READIN.XGP[BOO,JMC] - www.SailDart.org

perm filename READIN.XGP[BOO,JMC] blob sn#525098 filedate 1980-07-22 generic text, type T, neo UTF8
/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#3=SUB/FONT#4=SUP/FONT#5=GACS25/FONT#6=FIX20/FONT#7=SYMB30[FNT,CLT]/FONT#8=FIX25/FONT#11=GRFX25/FONT#12=GRFX35/FONT#9=BEESIX















␈↓ ↓H␈↓	␈↓ ε≥LISP


␈↓ ↓H␈↓	␈↓ ∧eProgramming and Proving




␈↓ ↓H␈↓	␈↓ ¬~CHAPTER READIN










␈↓ ↓H␈↓␈↓ ¬SCopyright ␈↓π@␈↓ 1980

␈↓ ↓H␈↓␈↓ ∧XJohn McCarthy and Carolyn Talcott


␈↓ ↓H␈↓␈↓ ¬GStanford University



␈↓ ↓H␈↓␈↓ ∧_This version printed at 20:43 on July 22, 1980.
␈↓ ↓H␈↓␈↓ εH␈↓ ?i


␈↓ ↓H␈↓α␈↓ ¬NTable of Contents



␈↓ ↓H␈↓␈↓ 	Page



␈↓ ↓H␈↓I␈↓ α_INTRODUCTION TO LISP

␈↓ ↓H␈↓␈↓ α81␈↓ αxLists.␈↓ βx   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓ ≠   1

␈↓ ↓H␈↓␈↓ α82␈↓ αxAtoms.␈↓ βx   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓ ≠   2

␈↓ ↓H␈↓␈↓ α83␈↓ αxList structures.␈↓ ∧8   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓ ≠   3

␈↓ ↓H␈↓␈↓ α84␈↓ αxS-expressions.␈↓ ∧8   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓ ≠   4

␈↓ ↓H␈↓␈↓ α85␈↓ αxThe basic functions and predicates on S-expressions.␈↓ λ8   .   .   .   .   .   .   .   .   .␈↓ ≠   7

␈↓ ↓H␈↓␈↓ α86␈↓ αxConditional terms.␈↓ ∧x   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓    10

␈↓ ↓H␈↓␈↓ α87␈↓ αxPropositional terms.␈↓ ∧x   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓    13

␈↓ ↓H␈↓␈↓ α88␈↓ αxRecursive function definitions.␈↓ ¬x   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓    14

␈↓ ↓H␈↓␈↓ α89␈↓ αxNumerical computation.␈↓ ¬8   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓    19

␈↓ ↓H␈↓␈↓ α810␈↓ αxBitwise Boolean Operations␈↓ ¬x   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓    21

␈↓ ↓H␈↓␈↓ α811␈↓ αxLambda expressions and functions with functions as arguments.␈↓ 	8   .   .   .   .   .␈↓    23

␈↓ ↓H␈↓␈↓ α812␈↓ αxLabel.␈↓ βx   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓    26

␈↓ ↓H␈↓␈↓ α813␈↓ αxThe function ␈↓↓eval.␈↓␈↓ ∧x   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .␈↓    27


␈↓ ↓H␈↓FUNCTION INDEX


␈↓ ↓H␈↓DEFINED LABELS
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓α␈↓ επChapter I

␈↓ ↓H␈↓α␈↓ ¬εINTRODUCTION TO LISP


␈↓ ↓H␈↓        LISP␈α⊂is␈α⊂a␈α∂language␈α⊂for␈α⊂writing␈α∂programs␈α⊂that␈α⊂do␈α∂symbolic␈α⊂computation.␈α⊂ Information␈α∂is
␈↓ ↓H␈↓coded␈α∩or␈α∩represented␈α∩as␈α∩S-expressions.␈α∩ A␈α∩LISP␈α∩program␈α∩can␈α∩also␈α∩be␈α∩represented␈α∩as␈α∩an␈α∩S-
␈↓ ↓H␈↓expression.␈α∞ This␈α∂gives␈α∞LISP␈α∞the␈α∂special␈α∞ability␈α∞to␈α∂easily␈α∞manipulate␈α∞programs␈α∂as␈α∞well␈α∂as␈α∞other
␈↓ ↓H␈↓sorts␈αof␈αsymbolic␈αdata.␈α In␈α
this␈αchapter␈αwe␈αdescribe␈αnotation␈α
for␈αlists␈αand␈αS-expressions,␈αshow␈α
how
␈↓ ↓H␈↓they␈α∪are␈α∪represented␈α∪in␈α∩a␈α∪computer␈α∪as␈α∪list␈α∪structures,␈α∩and␈α∪describe␈α∪the␈α∪basic␈α∪functions␈α∩and
␈↓ ↓H␈↓predicates␈α∂on␈α⊂the␈α∂domain␈α⊂of␈α∂S-expressions␈α⊂in␈α∂terms␈α⊂of␈α∂the␈α⊂computer␈α∂representation.␈α⊂ We␈α∂then
␈↓ ↓H␈↓describe the basic constructs of LISP and show how they are used to form LISP programs.



␈↓ ↓H␈↓1.  ␈↓αLists.␈↓


␈↓ ↓H␈↓        We␈αbegin␈αwith␈αsome␈αexamples.␈α The␈α
most␈αcommon␈αform␈αof␈αS-expression␈αis␈αthe␈α
list.␈αFigure
␈↓ ↓H␈↓1␈α∞shows␈α∞some␈α∞examples␈α∞of␈α∞lists.␈α∞ The␈α∞list␈α∞(i)␈α∞has␈α∞four␈α∞elements,␈α∞one␈α∞of␈α∞which␈α∞is␈α∂repeated.␈α∞ The
␈↓ ↓H␈↓list␈α(ii)␈αhas␈αfour␈αelements␈αone␈αof␈αwhich␈αis␈αitself␈αa␈αlist.␈α The␈αlist␈α(iii)␈αhas␈αone␈αelement.␈α The␈αlist␈α(iv)
␈↓ ↓H␈↓also has one element which itself is a list.  The list (v) has no elements; it is also written ␈↓¬NIL␈↓.


␈↓ ↓H␈↓␈↓ ¬_(i)␈↓ ε8␈↓¬(A B A E)    ␈↓
␈↓ ↓H␈↓␈↓ ¬_(ii)␈↓ ε8␈↓¬(A B (C D) E)␈↓
␈↓ ↓H␈↓␈↓ ¬_(iii)␈↓ ε8␈↓¬(A)          ␈↓
␈↓ ↓H␈↓␈↓ ¬_(iv)␈↓ ε8␈↓¬((A B C D))  ␈↓
␈↓ ↓H␈↓␈↓ ¬_(v)␈↓ ε8␈↓¬()           ␈↓

␈↓ ↓H␈↓␈↓ ¬∪␈↓αFigure 1.␈↓  Examples of lists.



␈↓ ↓H␈↓        Figure␈α∩2␈α∪shows␈α∩how␈α∩symbolic␈α∪information␈α∩can␈α∩be␈α∪represented␈α∩by␈α∩lists.␈α∪ Each␈α∩example
␈↓ ↓H␈↓consists␈αof␈αa␈α
list␈αand␈αa␈α
"mathematical"␈αrepresentation␈αof␈α
the␈αsame␈αinformation.␈α
 Examples␈α(i)-(iv)
␈↓ ↓H␈↓represent␈α⊂familiar␈α⊂mathematical␈α⊂and␈α⊃logical␈α⊂expressions.␈α⊂ The␈α⊂list␈α⊃(v)␈α⊂is␈α⊂used␈α⊂to␈α⊃represent␈α⊂the
␈↓ ↓H␈↓network␈α∩or␈α∩graph␈α∩shown␈α∩according␈α∩to␈α∩a␈α∩scheme␈α∩whereby␈α∩there␈α∩is␈α∩a␈α∩sublist␈α∩for␈α∩each␈α∩vertex
␈↓ ↓H␈↓consisting of the vertex itself followed by the vertices to which it is connected.

␈↓ ↓H␈↓        The␈αelements␈αof␈αa␈αlist␈αare␈αsurrounded␈αby␈αparentheses␈αand␈αseparated␈αby␈αspaces.␈α A␈α
list␈αmay
␈↓ ↓H␈↓have␈α
any␈αnumber␈α
of␈α
terms␈αand␈α
any␈αof␈α
these␈α
terms␈αmay␈α
themselves␈αbe␈α
lists.␈α
 In␈αthis␈α
case,␈αthe␈α
spaces
␈↓ ↓H␈↓surrounding␈α∞a␈α∞sublist␈α∞may␈α∂be␈α∞omitted,␈α∞and␈α∞extra␈α∞spaces␈α∂between␈α∞elements␈α∞of␈α∞a␈α∞list␈α∂are␈α∞allowed.
␈↓ ↓H␈↓Thus  ␈↓¬(A B(C  D)    E)␈↓  ␈αand  ␈↓¬(A B (C D) E)␈↓  are␈αslightly␈αdifferent␈αways␈αof␈αwriting␈αthe␈αsame
␈↓ ↓H␈↓list.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 92





␈↓ ↓H␈↓␈↓ αX(i)␈↓ βx␈↓¬(PLUS X Y)␈↓
␈↓ ↓H␈↓␈↓ βx␈↓↓x + y␈↓

␈↓ ↓H␈↓␈↓ αX(ii)␈↓ βx␈↓¬(PLUS (TIMES X Y) X 3)␈↓
␈↓ ↓H␈↓␈↓ βx␈↓↓xy + x + 3␈↓.

␈↓ ↓H␈↓␈↓ αX(iii)␈↓ βx␈↓¬(EXIST X (ALL Y (IMPLIES (P X) (P Y))))␈↓
␈↓ ↓H␈↓␈↓ βx␈↓↓∃x: ∀y: [P(x)⊃P(y)]␈↓.

␈↓ ↓H␈↓␈↓ αX(iv)␈↓ βx␈↓¬(INTEGRAL 0 ∞ (TIMES (EXP (TIMES I X Y)) (F X)) X)␈↓
␈↓ ↓H␈↓␈↓ βx␈↓π&␈↓β0␈↓∧␈↓#
∞␈↓#␈↓↓e␈↓∧ixy␈↓↓f(x)dx␈↓.

␈↓ ↓H␈↓␈↓ αX(v)␈↓ βx␈↓¬((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E))␈↓

␈↓"␈↓ ↓H␈↓␈↓ ε8C
␈↓"␈↓ ↓H␈↓␈↓ ε_≤'~`≥
␈↓"␈↓ ↓H␈↓␈↓ ¬x≤'  ~  `≥
␈↓"␈↓ ↓H␈↓␈↓ ¬8B ≤'    ~    `≥ E
␈↓"␈↓ ↓H␈↓␈↓ ∧(A αααααααα␈↓ ¬H'␈↓ ¬H≥␈↓ ε8~␈↓ π(≤␈↓ π(`αααααααα F
␈↓"␈↓ ↓H␈↓␈↓ ¬X`≥    ~    ≤'
␈↓"␈↓ ↓H␈↓␈↓ ¬x`≥  ~  ≤'
␈↓"␈↓ ↓H␈↓␈↓ ε_`≥~≤'
␈↓"␈↓ ↓H␈↓␈↓ ε8D


␈↓ ↓H␈↓␈↓ ∧5␈↓αFigure 2.␈↓  Information represented as lists.





␈↓ ↓H␈↓2.  ␈↓αAtoms.␈↓


␈↓ ↓H␈↓        The␈α
expressions␈α
␈↓¬A,␈α
B,␈α∞X,␈α
Y,␈α
3,␈α
PLUS␈↓,␈α∞and␈α
␈↓¬ALL␈↓␈α
occurring␈α
in␈α
the␈α∞lists␈α
in␈α
Figures␈α
1␈α∞and␈α
2
␈↓ ↓H␈↓are␈αcalled␈αatoms.␈α In␈αgeneral,␈αan␈αatom␈αis␈αwritten␈αas␈αa␈αsequence␈αof␈αcapital␈αletters,␈αdigits,␈αand␈αspecial
␈↓ ↓H␈↓characters␈α
with␈α
certain␈α
exclusions.␈α
 The␈α
exclusions␈αare␈α
<space>,␈α
<carriage␈α
return>,␈α
and␈α
the␈αother
␈↓ ↓H␈↓non-printing␈αcharacters,␈α
and␈αalso␈α
the␈αparentheses,␈α
brackets,␈αsemi-colon,␈α
and␈αcomma.␈α Numbers␈α
are
␈↓ ↓H␈↓expressed␈α_as␈α→signed␈α_decimal␈α→or␈α_octal␈α_numbers,␈α→the␈α_exact␈α→convention␈α_depending␈α→on␈α_the
␈↓ ↓H␈↓implementation.␈α Floating␈α
point␈αnumbers␈α
are␈αwritten␈α
with␈αdecimal␈α
points␈αand,␈α
when␈αappropriate,
␈↓ ↓H␈↓an␈α↔exponent␈α↔notation␈α↔depending␈α↔on␈α⊗the␈α↔implementation.␈α↔ The␈α↔reader␈α↔should␈α↔consult␈α⊗the
␈↓ ↓H␈↓programmer's␈αmanual␈αfor␈αthe␈αLISP␈αimplementation␈αhe␈αintends␈αto␈αuse.␈α Some␈αfurther␈αexamples␈αof
␈↓ ↓H␈↓atoms␈α∪are␈α∪shown␈α∪in␈α∪Figure␈α∪3.␈α∀ From␈α∪such␈α∪atoms␈α∪we␈α∪can␈α∪form␈α∪lists␈α∀like␈α∪␈↓¬((345 3.14159 -
␈↓ ↓H␈↓¬47) A307B THE-LAST-TRUMP -45.21)␈↓.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 93



␈↓ ↓H␈↓␈↓ ¬X␈↓¬THE-LAST-TRUMP␈↓
␈↓ ↓H␈↓␈↓ ¬X␈↓¬A307B         ␈↓
␈↓ ↓H␈↓␈↓ ¬X␈↓¬345           ␈↓
␈↓ ↓H␈↓␈↓ ¬X␈↓¬-47           ␈↓
␈↓ ↓H␈↓␈↓ ¬X␈↓¬-45.21        ␈↓
␈↓ ↓H␈↓␈↓ ¬X␈↓¬3.14159       ␈↓

␈↓ ↓H␈↓␈↓ ¬¬␈↓αFigure 3.␈↓  Examples of atoms.





␈↓ ↓H␈↓3.  ␈↓αList structures.␈↓


␈↓ ↓H␈↓        Atoms␈α∞and␈α∞lists␈α∞are␈α∞represented␈α∞in␈α∞the␈α∂memory␈α∞of␈α∞the␈α∞computer␈α∞by␈α∞list␈α∞structures.␈α∂ A␈α∞list
␈↓ ↓H␈↓structure␈α
is␈α
a␈α
collection␈αof␈α
memory␈α
units␈α
called␈α
␈↓↓cons-cells.␈↓␈α  A␈α
cons-cell␈α
generally␈α
consists␈α
of␈αone␈α
or
␈↓ ↓H␈↓possibly␈αtwo␈αconsecutive␈αcomputer␈αwords.␈α It␈αis␈αdivided␈αinto␈αtwo␈αparts,␈αthe␈αa-part␈αand␈αthe␈αd-part,
␈↓ ↓H␈↓with␈αeach␈αpart␈αbeing␈αcapable␈αof␈αcontaining␈αan␈αaddress␈αin␈αmemory.␈αThe␈αlist␈αstructure␈αrepresenting
␈↓ ↓H␈↓a␈αlist␈αcontains␈αa␈αcons-cell␈αfor␈αeach␈αelement␈αof␈αthe␈αlist.␈α The␈αa-part␈αof␈αthe␈αcell␈αcontains␈αthe␈αaddress
␈↓ ↓H␈↓of␈α
the␈α
list␈α
structure␈α
representing␈α
the␈α
element␈α
and␈α
the␈α
d-part␈α
contains␈α
the␈α
address␈α
of␈α
the␈α
cell␈αfor␈α
the
␈↓ ↓H␈↓next␈α∂element␈α⊂of␈α∂the␈α⊂list.␈α∂ These␈α⊂addresses␈α∂are␈α⊂sometimes␈α∂called␈α⊂pointers␈α∂as␈α⊂they␈α∂``point''␈α⊂to␈α∂the
␈↓ ↓H␈↓component list structures.

␈↓ ↓H␈↓A␈α
diagram␈α
shows␈α∞this␈α
more␈α
clearly␈α∞than␈α
words.␈α
 Figure 4␈α∞shows␈α
the␈α
list␈α∞structure␈α
corresponding
␈↓ ↓H␈↓to the list   ␈↓¬(PLUS (TIMES X Y) X 3)␈↓   (which might represent the expression   ␈↓↓xy + x + 3␈↓).
␈↓"
␈↓"
␈↓"␈↓ ↓H␈↓            ⊂αααπααα⊃     ⊂αααπααα⊃     ⊂αααπααα⊃     ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓      ααααα→~   ~   εαααα→~   ~   εαααα→~   ~   εαααα→~   ~   εααααααα⊃
␈↓"␈↓ ↓H␈↓            %απα∀ααα$     %απα∀ααα$     %απα∀ααα$     %απα∀ααα$       ~
␈↓"␈↓ ↓H␈↓              ↓             ~             ~             ↓             ~
␈↓"␈↓ ↓H␈↓             PLUS           ~             ~             3             ~
␈↓"␈↓ ↓H␈↓                            ~  ⊂αααπααα⊃  ~  ⊂αααπααα⊃     ⊂αααπααα⊃  ~
␈↓"␈↓ ↓H␈↓                            %α→~   ~   εααβα→~   ~   εαααα→~   ~   ~  ~
␈↓"␈↓ ↓H␈↓                               %απα∀ααα$  ~  %απα∀ααα$     %απα∀απα$  ~
␈↓"␈↓ ↓H␈↓                                 ↓        ~    ~             ↓   ~    ~
␈↓"␈↓ ↓H␈↓                               TIMES      %απαα$             Y   %ααπα$
␈↓"␈↓ ↓H␈↓                                            ↓                       ↓
␈↓"␈↓ ↓H␈↓                                            X                      NIL
␈↓"
␈↓ ↓H␈↓␈↓ αd␈↓αFigure 4.␈↓  Representation of ␈↓¬(PLUS (TIMES X Y) X 3)␈↓ as a list structure.␈↓¬



␈↓ ↓H␈↓        A␈αprogram␈αrefers␈αto␈αa␈αlist␈αby␈αthe␈αaddress␈αof␈αthe␈αcell␈αfor␈αits␈αfirst␈αelement.␈α According␈αto␈αthis
␈↓ ↓H␈↓convention,␈α
we␈α
see␈α
that␈αthe␈α
a-part␈α
of␈α
this␈αcell␈α
is␈α
the␈α
first␈αelement␈α
of␈α
the␈α
list␈αand␈α
the␈α
d-part␈α
is␈αa
␈↓ ↓H␈↓pointer␈αto␈αa␈αsublist␈αformed␈αby␈αdeleting␈αthe␈αfirst␈αelement.␈α Thus␈αthe␈αfirst␈αword␈αof␈αthe␈αlist␈αstructure
␈↓ ↓H␈↓of␈α
Figure 4␈α
contains␈α
a␈α
pointer␈α
to␈α
the␈α∞list␈α
structure␈α
representing␈α
the␈α
atom␈α
␈↓¬PLUS␈↓,␈α
 while␈α∞its␈α
d-part
␈↓ ↓H␈↓points␈α
to␈α
the␈α
list␈α
␈↓¬((TIMES X Y) X 3)␈↓.␈α
 The␈α
second␈α
word␈α
contains␈α
the␈α
list␈α∞structure␈α
representing
␈↓ ↓H␈↓␈↓¬(TIMES X Y)␈↓␈αin␈αits␈αa-part␈αand␈αthe␈αlist␈αstructure␈αrepresenting␈α␈↓¬(X 3)␈↓␈αin␈αits␈αd-part.␈α The␈αlast␈αword
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 94


␈↓ ↓H␈↓points␈α⊂to␈α∂the␈α⊂atom␈α∂␈↓¬3␈↓␈α⊂in␈α∂its␈α⊂a-part␈α∂and␈α⊂has␈α⊂a␈α∂pointer␈α⊂to␈α∂the␈α⊂atom␈α∂␈↓¬NIL␈↓␈α⊂in␈α∂its␈α⊂d-part.␈α⊂ This␈α∂is
␈↓ ↓H␈↓consistent with the convention that ␈↓¬NIL␈↓ represents the null list.

␈↓ ↓H␈↓        Atoms␈αare␈αrepresented␈αby␈αthe␈αaddresses␈αof␈αtheir␈αproperty␈αlists␈αwhich␈αare␈αlist␈αstructures␈αof␈αa
␈↓ ↓H␈↓special␈α∂kind␈α⊂depending␈α∂on␈α∂the␈α⊂implementation.␈α∂ (In␈α⊂some␈α∂implementations,␈α∂the␈α⊂first␈α∂word␈α⊂of␈α∂a
␈↓ ↓H␈↓property␈α
list␈α
is␈α
in␈α
a␈α
special␈αarea␈α
of␈α
memory,␈α
in␈α
others␈α
the␈αfirst␈α
word␈α
is␈α
distinguished␈α
by␈α
sign,␈αin
␈↓ ↓H␈↓still␈αothers␈αit␈αhas␈αa␈αspecial␈αa-part.␈α For␈αbasic␈αLISP␈αprogramming,␈αit␈αis␈αenough␈αto␈αknow␈αthat␈αatoms
␈↓ ↓H␈↓are␈α
distinguishable␈α
from␈α
other␈α
list␈α
structures␈α∞by␈α
a␈α
predicate␈α
called␈α
␈↓αat␈↓.)␈α
Each␈α
atom␈α∞is␈α
represented
␈↓ ↓H␈↓uniquely.  In the diagram they are simply refered to by name.

␈↓ ↓H␈↓A␈αpartial␈αdump␈αof␈αthe␈αmemory␈αof␈αa␈αcomputer␈αcontaining␈αthe␈αlist␈αstructure␈αof␈αFigure 4␈αmight␈αlook
␈↓ ↓H␈↓as␈αshown␈αin␈αFigure 5.␈α Here␈α
␈↓X␈↓␈αdenotes␈αthe␈αaddress␈αof␈αthe␈α
property␈αlist␈αof␈αthe␈αatom␈αnamed␈α
␈↓¬X␈α␈↓and
␈↓ ↓H␈↓␈↓/3␈↓␈αdenotes␈αthat␈αof␈αthe␈αatom␈αnamed␈α␈↓¬3␈↓.␈α Notice␈αthat␈αthe␈αaddresses␈αof␈αconsecutive␈αlist␈αelements␈αneed
␈↓ ↓H␈↓not␈αbe␈αconsecutive.␈α Also␈αthe␈αlast␈αword␈αof␈αa␈αlist␈αcannot␈αhave␈αthe␈αaddress␈αof␈αa␈αnext␈αword␈αin␈αits␈αd-
␈↓ ↓H␈↓part since there isn't any next word, so it has the address of a special atom called ␈↓¬NIL␈↓.

␈↓ ↓H␈↓        address    a-part    d-part        address    a-part    d-part
␈↓ ↓H␈↓        _______    ______    ______        _______    ______    ______

␈↓ ↓H␈↓            86      TIMES       87           1000      PLUS      1001
␈↓ ↓H␈↓            87          X       88           1001        86      1002
␈↓ ↓H␈↓            88          Y      NIL           1002         X      2653
␈↓ ↓H␈↓                                             2653        /3       NIL

␈↓ ↓H␈↓␈↓ βG␈↓αFigure 5.␈↓  A memory map for the list structure of Figure 4.





␈↓ ↓H␈↓4.  ␈↓αS-expressions.␈↓


␈↓ ↓H␈↓        When␈α∪we␈α∪examine␈α∩the␈α∪way␈α∪list␈α∩structures␈α∪represent␈α∪lists␈α∩we␈α∪see␈α∪a␈α∪curious␈α∩asymmetry.
␈↓ ↓H␈↓Namely,␈αthe␈αa-part␈αof␈αa␈αlist␈αword␈αcan␈αcontain␈αan␈αatom␈αor␈αa␈αlist,␈αbut␈αthe␈αd-part␈αcan␈αcontain␈αonly␈α
a
␈↓ ↓H␈↓list␈α
or␈αthe␈α
special␈αatom␈α
␈↓¬NIL␈↓.␈α This␈α
restriction␈α
is␈αquite␈α
unnatural␈αfrom␈α
the␈αcomputing␈α
point␈αof␈α
view,
␈↓ ↓H␈↓and␈αwe␈αshall␈α
allow␈αarbitrary␈αatoms␈α
to␈αinhabit␈αthe␈α
d-parts␈αof␈αwords,␈α
but␈αthen␈αwe␈α
must␈αgeneralize
␈↓ ↓H␈↓the␈α
way␈α
list␈αstructures␈α
are␈α
expressed␈αas␈α
character␈α
strings.␈α
To␈αdo␈α
this,␈α
we␈αintroduce␈α
the␈α
notion␈αof␈α
S-
␈↓ ↓H␈↓expression.

␈↓ ↓H␈↓        An␈α
S-expression␈α
is␈α
either␈α
an␈α
atom␈α
or␈α
a␈α
pair␈α
of␈α
S-expressions.␈α
 To␈α
write␈α
a␈α
non-atomic␈α
S-
␈↓ ↓H␈↓expression␈α
we␈αwrite␈α
the␈α
pair␈αof␈α
subexpression␈αseparated␈α
by␈α
" . "␈αand␈α
surrounded␈α
by␈αparentheses.
␈↓ ↓H␈↓In BNF this rule is given by:

␈↓ ↓H␈↓␈↓ β	        <S-expression> ::= <atom> | (<S-expression> . <S-expression>).

␈↓ ↓H␈↓Figure 6 shows some examples of S-expressions.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 95



␈↓ ↓H␈↓␈↓ ¬␈↓¬A                        ␈↓
␈↓ ↓H␈↓␈↓ ¬␈↓¬(A . B)                  ␈↓
␈↓ ↓H␈↓␈↓ ¬␈↓¬(A . (B . A))            ␈↓
␈↓ ↓H␈↓␈↓ ¬␈↓¬(PLUS . (X . (Y . NIL))) ␈↓
␈↓ ↓H␈↓␈↓ ¬␈↓¬(3 . 3.4)                ␈↓

␈↓ ↓H␈↓␈↓ ∧R␈↓αFigure 6.␈↓  Examples of S-expressions.



␈↓ ↓H␈↓In␈α
writing␈α
an␈α
S-expression,␈α
the␈α
spaces␈α
around␈α
the␈α" . "␈α
may␈α
be␈α
omitted␈α
when␈α
this␈α
will␈α
not␈αcause
␈↓ ↓H␈↓confusion.␈α The␈αonly␈αpossible␈αconfusion␈αis␈αof␈αthe␈αdot␈αseparator␈αwith␈αa␈αdecimal␈αpoint␈α
in␈αnumbers.
␈↓ ↓H␈↓Thus,␈αin␈αthe␈αabove␈αcases,␈αwe␈αmay␈αwrite␈α␈↓¬(A.B)␈↓,␈α␈↓¬(A.(B.A))␈↓,␈αand␈α␈↓¬(PLUS.(X.(Y.NIL)))␈↓,␈αbut␈αif␈αwe
␈↓ ↓H␈↓wrote ␈↓¬(3.3.4)␈↓ confusion would result.

␈↓ ↓H␈↓        In␈αthe␈αmemory␈αof␈αa␈αcomputer,␈αan␈αS-expression␈αis␈αrepresented␈αby␈αthe␈αaddress␈αof␈α
a␈αcons-cell
␈↓ ↓H␈↓whose␈α
a-part␈α
points␈αto␈α
the␈α
first␈αelement␈α
of␈α
the␈α
pair␈αand␈α
whose␈α
d-part␈αpoints␈α
to␈α
the␈αsecond␈α
element
␈↓ ↓H␈↓of␈α_the␈α_pair.␈α_ Thus,␈α_the␈α_S-expressions␈α_␈↓¬(A.B)␈↓,␈α_␈↓¬(A.(B.A))␈↓,␈α_and␈α_␈↓¬(PLUS.(X.(Y.NIL)))␈↓␈α_are
␈↓ ↓H␈↓represented by the list structures of Figure 7.
␈↓"
␈↓"
␈↓"␈↓ ↓H␈↓            ⊂αααπααα⊃                             ⊂αααπααα⊃     ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓       αααα→~   ~   ~                        αααα→~   ~   εαααα→~   ~   ~
␈↓"␈↓ ↓H␈↓            %απα∀απα$                             %απα∀ααα$     %απα∀απα$
␈↓"␈↓ ↓H␈↓              ↓   ↓                                 ~             ↓   ~
␈↓"␈↓ ↓H␈↓              A   B                                 ~             B   ~
␈↓"␈↓ ↓H␈↓                                                    ~                 ~
␈↓"␈↓ ↓H␈↓                                                    ~                 ~
␈↓"␈↓ ↓H␈↓                                                    %ααααααααπαααααααα$
␈↓"␈↓ ↓H␈↓                                                             ↓
␈↓"␈↓ ↓H␈↓                                                             A
␈↓"
␈↓"␈↓ ↓H␈↓            ⊂αααπααα⊃     ⊂αααπααα⊃     ⊂αααπααα⊃
␈↓"␈↓ ↓H␈↓       αααα→~   ~   εαααα→~   ~   εαααα→~   ~   ~
␈↓"␈↓ ↓H␈↓            %απα∀ααα$     %απα∀ααα$     %απα∀απα$
␈↓"␈↓ ↓H␈↓              ↓             ↓             ↓   ↓
␈↓"␈↓ ↓H␈↓             PLUS           X             Y  NIL
␈↓"
␈↓"
␈↓ ↓H␈↓␈↓ βD␈↓αFigure 7.␈↓  Representation of S-expressions as list structures.



␈↓ ↓H␈↓        Note␈α∩that␈α∩the␈α∩list␈α∩␈↓¬(PLUS X Y)␈↓␈α∩and␈α∩the␈α∩S-expression␈α∩ ␈↓¬(PLUS . (X . (Y . NIL)))␈↓␈α∩are
␈↓ ↓H␈↓represented␈αin␈α
memory␈αby␈α
the␈αsame␈α
list␈αstructure.␈α
 The␈αsimplest␈α
way␈αto␈α
treat␈αthis␈α
is␈αto␈α
regard␈αS-
␈↓ ↓H␈↓expressions␈α
as␈αprimary␈α
and␈αlists␈α
as␈αspecial␈α
kinds␈αof␈α
S-expressions,␈αnamely␈α
those␈αthat␈α
never␈αhave
␈↓ ↓H␈↓any␈α
atom␈α
but␈α
␈↓¬NIL␈↓␈α
as␈α
the␈αsecond␈α
part␈α
of␈α
a␈α
pair.␈α
 The␈αlist␈α
notation␈α
can␈α
then␈α
be␈α
considered␈α
as␈αan
␈↓ ↓H␈↓abbreviated␈α∞way␈α
of␈α∞writing␈α
these␈α∞S-expressions,␈α
Thus,␈α∞the␈α
list␈α∞notation␈α
␈↓¬(A B . . . Z)␈↓␈α∞may␈α
be
␈↓ ↓H␈↓regarded␈α?␈α↔as␈α?␈α_an␈α?␈α↔abbreviation␈α?␈α_of␈α?␈α↔the␈α?␈α_S-expression␈α?␈α↔notation
␈↓ ↓H␈↓␈↓¬(A . (B . (C . (... (Z . NIL) ...))))␈↓.␈α∪ Note␈α∪that␈α∪the␈α∪a-part␈α∪of␈α∪a␈α∪list␈α∪can␈α∪be␈α∪any␈α∪S-
␈↓ ↓H␈↓expression,␈αbut␈αthe␈αd-part␈α
of␈αa␈αlist␈αmust␈αbe␈α
a␈αlist␈αand␈αand␈αthe␈α
only␈αatomic␈αlist␈αis␈α␈↓¬NIL␈↓.␈α
 In␈αgiving
␈↓ ↓H␈↓input␈α
to␈α∞LISP,␈α
either␈α∞the␈α
list␈α∞form␈α
or␈α∞the␈α
S-expression␈α∞form␈α
may␈α∞be␈α
used␈α∞for␈α
lists.␈α∞ On␈α
output,
␈↓ ↓H␈↓LISP␈αwill␈αprint␈α
a␈αlist␈αstructure␈α
as␈αa␈αlist␈α
as␈αfar␈αas␈α
it␈αcan,␈αotherwise␈α
as␈αan␈αS-expression.␈α Thus,␈α
some
␈↓ ↓H␈↓list␈α
structures␈αwill␈α
be␈αprinted␈α
in␈αa␈α
mixed␈αnotation,␈α
e.g.␈α␈↓¬((A . B) (C . D) (3))␈↓.␈α
 Some␈αLISPs␈α
use
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 96


␈↓ ↓H␈↓an␈α
"extended"␈αlist␈α
notation␈αfor␈α
printing␈α
S-expressions␈αwhich␈α
minimizes␈αthe␈α
number␈αof␈α
parentheses
␈↓ ↓H␈↓and␈α⊗dots␈α↔printed.␈α⊗  In␈α↔this␈α⊗notation␈α⊗␈↓¬(A . (B . (C . D)))␈↓␈α↔would␈α⊗print␈α↔as␈α⊗␈↓¬(A B C . D)␈↓.
␈↓ ↓H␈↓(Programs for reading and printing S-expressions in the two notations are given in Chapter VI.)


␈↓ ↓H␈↓α␈↓ ε
Exercises

␈↓ ↓H␈↓        1.␈α≠If␈α≠we␈α≠represent␈α≠sums␈α≠and␈α≠products␈α≠as␈α≠indicated␈α≠above␈α≠and␈α≠use␈α~␈↓¬(MINUS X)␈↓,
␈↓ ↓H␈↓␈↓¬(QUOTIENT X Y)␈↓, and ␈↓¬(POWER X Y)␈↓ as representations of ␈↓↓-x,␈↓ ␈↓↓x/y,␈↓ and ␈↓↓x␈↓∧y␈↓ respectively, then

␈↓ ↓H␈↓                a. What do the following lists represent?

␈↓ ↓H␈↓␈↓ ∧␈↓↓␈↓¬(QUOTIENT 2 (POWER (PLUS X (MINUS Y)) 3))␈↓↓␈↓
␈↓ ↓H␈↓␈↓ βp␈↓↓␈↓¬(PLUS -2 (MINUS 2) (TIMES X (POWER Y 3.3)))␈↓↓␈↓

␈↓ ↓H␈↓                b. How are the expressions ␈↓↓xyz+3(u+v)␈↓∧-3␈↓ and ␈↓↓(xy-yx)/(xy+yx)␈↓ to be represented?

␈↓ ↓H␈↓        2. In the above mentioned graph notation, what graph is represented by the list

␈↓ ↓H␈↓␈↓ αZ␈↓¬((A D E F) (B D E F) (C D E F) (D A B C) (E A B C) (F A B C))␈↓?

␈↓ ↓H␈↓        3.␈α
Write␈α
the␈αlist␈α
␈↓¬(PLUS␈α
(TIMES␈αX␈α
Y)␈α
X␈α3)␈↓␈α
as␈α
an␈αS-expression.␈α
 This␈α
is␈α
sometimes␈αreferred
␈↓ ↓H␈↓to as "dot-notation".

␈↓ ↓H␈↓        4.  Write the following S-expressions in list notation to whatever extent is possible:

␈↓ ↓H␈↓                a. ␈↓¬(A . NIL)␈↓
␈↓ ↓H␈↓                b. ␈↓¬(A . B)␈↓
␈↓ ↓H␈↓                c. ␈↓¬((A . NIL) . B)␈↓
␈↓ ↓H␈↓                d. ␈↓¬((A . B) . ((C . D) . NIL))␈↓.

␈↓ ↓H␈↓        5.␈α
How␈α
would␈α
you␈α
represent␈α
polynomials␈α
in␈αone␈α
variable␈α
as␈α
lists?␈α
 Can␈α
you␈α
think␈α
of␈αmore
␈↓ ↓H␈↓that␈α
one␈α∞way?␈α
 How␈α∞would␈α
you␈α∞represent␈α
polynomials␈α∞in␈α
several␈α∞variables?␈α
 Can␈α∞you␈α
tell␈α∞if␈α
two
␈↓ ↓H␈↓lists represent the same polynomial?

␈↓ ↓H␈↓        (The␈α⊂next␈α⊂two␈α⊂mathematical␈α⊂exercises␈α⊃are␈α⊂unconnected␈α⊂with␈α⊂subsequent␈α⊂material␈α⊃in␈α⊂this
␈↓ ↓H␈↓book.)

␈↓ ↓H␈↓        6.␈αProve␈αthat␈αthe␈αnumber␈αof␈α"shapes"␈αof␈αS-expressions␈αwith␈α␈↓↓n␈↓␈αatoms␈αis␈α␈↓↓(2n␈α-␈α2)!/(n!(n␈α-␈α1)!)␈↓.
␈↓ ↓H␈↓(The␈α∩two␈α∩shapes␈α∩of␈α∩S-expressions␈α∩with␈α∩three␈α∩atoms␈α∩are␈α∩␈↓¬(A.(B.C))␈↓␈α∩and␈α∪␈↓¬((A.B).C)␈↓.␈α∩ These
␈↓ ↓H␈↓numbers are called Catalan numbers.

␈↓ ↓H␈↓        7.␈αThe␈αabove␈αresult␈αcan␈αalso␈αbe␈αobtained␈αby␈αwriting␈α␈↓↓S = A + S␈↓π#␈↓↓S␈↓␈αas␈αan␈α"equation"␈αsatisfied
␈↓ ↓H␈↓by␈α∞the␈α∞set␈α∞of␈α
S-expressions␈α∞with␈α∞the␈α∞interpretation␈α
that␈α∞an␈α∞S-expression␈α∞is␈α
either␈α∞an␈α∞atom␈α∞or␈α
a
␈↓ ↓H␈↓pair␈αof␈α
S-expressions.␈α The␈αnext␈α
step␈αis␈α
to␈αregard␈αthe␈α
equation␈αas␈αthe␈α
quadratic␈α␈↓↓S␈↓∧2␈↓↓ - S + A␈α
=␈α0␈↓,
␈↓ ↓H␈↓solve␈α
it␈α
by␈α
the␈α
quadratic␈α
formula␈α
choosing␈α
the␈α
minus␈α
sign␈α
for␈α
the␈α
square␈α
root.␈α
 Then␈α
the␈αradical␈α
is
␈↓ ↓H␈↓regarded␈α
as␈α
the␈α
1/2␈α
power␈α
and␈α∞expanded␈α
by␈α
the␈α
binomial␈α
theorem.␈α
 Manipulating␈α∞the␈α
binomial
␈↓ ↓H␈↓coefficients␈α∞yields␈α∞the␈α∂above␈α∞formula␈α∞as␈α∞the␈α∂coefficient␈α∞of␈α∞␈↓↓A␈↓∧n␈↓␈α∞in␈α∂the␈α∞expansion.␈α∞ Why␈α∂does␈α∞this
␈↓ ↓H␈↓somewhat ill-motivated and irregular procedure give the right answer?
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 97


␈↓ ↓H␈↓5.  ␈↓αThe basic functions and predicates on S-expressions.␈↓


␈↓ ↓H␈↓        There␈α⊂are␈α⊂three␈α⊂basic␈α⊂functions␈α⊂on␈α⊂S-expressions:␈α⊂␈↓↓cons␈↓␈α⊂for␈α⊂constructing␈α⊂an␈α⊂S-expression
␈↓ ↓H␈↓from␈αtwo␈αgiven␈αS-expressions,␈αand␈α␈↓↓car␈↓␈αand␈α␈↓↓cdr␈↓␈αfor␈αselecting␈αthe␈αfirst␈αand␈αsecond␈αcomponents␈αof␈αa
␈↓ ↓H␈↓non-atomic␈α∩S-expression.␈α∩ There␈α∪are␈α∩two␈α∩predicates,␈α∪␈↓↓atom␈↓␈α∩for␈α∩testing␈α∪whether␈α∩or␈α∩not␈α∪an␈α∩S-
␈↓ ↓H␈↓expression␈αis␈α
atomic␈αand␈α
␈↓↓eq␈↓␈αfor␈α
testing␈αequality␈α
of␈αatoms.␈α
 In␈αthis␈α
section␈αwe␈α
will␈αdescribe␈αthe␈α
basic
␈↓ ↓H␈↓LISP␈αprograms␈αthat␈αcompute␈αthese␈αfunctions␈αand␈αpredicates␈αfrom␈αlist␈αstructure␈αrepresentations␈αof
␈↓ ↓H␈↓the␈αarguments.␈α All␈αLISP␈αprograms␈αfor␈αcomputing␈αfunctions␈αand␈αpredicates␈αon␈α
S-expressions␈αare
␈↓ ↓H␈↓built␈α⊃from␈α⊃these␈α⊃basic␈α⊃programs␈α⊃as␈α⊃will␈α⊃be␈α⊃explained␈α⊃in␈α⊃the␈α⊃sections␈α⊃following␈α⊃this.␈α⊃ This␈α⊃is
␈↓ ↓H␈↓analogous␈α
to␈αnumeric␈α
programs␈α
which␈αare␈α
based␈α
on␈αoperations␈α
computing␈α
the␈αarithmetic␈α
functions
␈↓ ↓H␈↓of␈αaddition␈αsubtraction,␈αmultiplication,␈αand␈αdivision,␈α
and␈αthe␈αarithmetic␈αpredicates␈αof␈αequality␈α
and
␈↓ ↓H␈↓comparison.

␈↓ ↓H␈↓        First␈α
we␈α∞introduce␈α
the␈α∞notation␈α
to␈α∞be␈α
used␈α∞for␈α
writing␈α∞LISP␈α
terms.␈α∞ This␈α
notation␈α∞will␈α
be
␈↓ ↓H␈↓extended␈α⊃in␈α⊂later␈α⊃sections␈α⊂to␈α⊃express␈α⊂LISP␈α⊃programs␈α⊂as␈α⊃well.␈α⊂ A␈α⊃LISP␈α⊂term␈α⊃is␈α⊃an␈α⊂expression
␈↓ ↓H␈↓intended␈α
to␈α
denote␈α
an␈α
S-expression␈α
(the␈α
value␈αof␈α
the␈α
term).␈α
 We␈α
will␈α
use␈α
two␈α
languages␈αfor␈α
writing
␈↓ ↓H␈↓LISP␈α⊗terms␈α⊗and␈α⊗programs␈α⊗-␈α∃␈↓↓internal␈α⊗language␈↓␈α⊗and␈α⊗␈↓↓external␈α⊗language␈↓.␈α⊗ Internal␈α∃language
␈↓ ↓H␈↓represents␈αLISP␈αterms␈αand␈αprograms␈αas␈αS-expressions.␈α Internal␈αlanguage␈αprograms␈αare␈αsomewhat
␈↓ ↓H␈↓harder␈α⊃for␈α⊃a␈α⊃person␈α⊃to␈α⊃read␈α∩and␈α⊃write,␈α⊃but␈α⊃it␈α⊃is␈α⊃easier␈α∩for␈α⊃a␈α⊃person␈α⊃to␈α⊃write␈α⊃a␈α∩program␈α⊃to
␈↓ ↓H␈↓manipulate␈α␈↓↓object␈↓␈α␈↓↓programs␈↓␈αwhen␈αthe␈αobject␈αprograms␈αare␈αin␈αinternal␈αlanguage␈α(e.g.␈αrepresented␈α
as
␈↓ ↓H␈↓S-expressions).␈α External␈αlanguage␈αis␈αa␈αnotation␈αthat␈α
is␈αcompact␈αand␈αeasier␈αfor␈αpeople␈αto␈αread␈α
and
␈↓ ↓H␈↓write.␈α However,␈αexternal␈αlanguage␈αprograms␈αare␈αnot␈αS-expressions,␈αand␈αtherefore␈αit␈αis␈αnot␈αeasy␈α
to
␈↓ ↓H␈↓write␈αLISP␈αprograms␈αto␈αgenerate,␈α
interpret,␈αcompile␈αor␈αotherwise␈αmanipulate␈αprograms␈α
written␈αin
␈↓ ↓H␈↓external␈α
language.␈α
 (An␈α
additional␈α
advantage␈α
of␈α
the␈α
external␈α
notation␈α
is␈α
that␈α
it␈α
very␈α
similar␈α
the
␈↓ ↓H␈↓language used to express facts about the abstract domain of S-expressions given in Chapter III).

␈↓ ↓H␈↓[Remark:␈α∞most␈α∞LISP␈α∞implementations␈α∞accept␈α∂only␈α∞internal␈α∞language␈α∞programs␈α∞rather␈α∂than␈α∞some
␈↓ ↓H␈↓form of external language.]

␈↓ ↓H␈↓        The␈α
simplest␈αLISP␈α
terms␈αare␈α
variables␈αand␈α
constants.␈α In␈α
the␈αexternal␈α
language␈αthe␈α
notation
␈↓ ↓H␈↓for␈α∂S-expression␈α∞constants␈α∂is␈α∞that␈α∂described␈α∞in␈α∂the␈α∞preceeding␈α∂sections.␈α∂ (S-expression␈α∞constants
␈↓ ↓H␈↓will␈α
always␈α
appear␈α
in␈α
the␈αspecial␈α
font␈α
used␈α
in␈α
the␈αprevious␈α
sections.)␈α
In␈α
the␈α
internal␈αlanguage␈α
there
␈↓ ↓H␈↓is␈α∞a␈α
possible␈α∞ambiguity␈α∞as␈α
to␈α∞whether␈α∞an␈α
S-expression␈α∞is␈α∞to␈α
represent␈α∞itself,␈α∞or␈α
the␈α∞value␈α∞of␈α
the
␈↓ ↓H␈↓LISP␈α⊂term␈α⊂that␈α⊂it␈α⊃represents␈α⊂(if␈α⊂any).␈α⊂ LISP␈α⊂takes␈α⊃the␈α⊂latter␈α⊂point␈α⊂of␈α⊂view.␈α⊃ An␈α⊂S-expression
␈↓ ↓H␈↓constant␈αis␈αrepresented␈αby␈αa␈αlist␈αwhose␈αfirst␈αelement␈αis␈αthe␈αatom␈α␈↓¬QOUTE␈α␈↓and␈αwhose␈αsecond␈αelement
␈↓ ↓H␈↓is␈α⊃the␈α⊃S-expression.␈α⊃ Thus␈α⊃the␈α∩S-expression␈α⊃constant␈α⊃␈↓¬<e>␈↓␈α⊃is␈α⊃represented␈α⊃by␈α∩the␈α⊃S-expression
␈↓ ↓H␈↓␈↓¬(QUOTE <e>)␈↓.

␈↓ ↓H␈↓        Variables␈α∞are␈α∞written␈α∞in␈α∞external␈α∞notation␈α∞as␈α∞lower␈α∞case␈α∞italic␈α∞identifiers.␈α∂ Frequently␈α∞just
␈↓ ↓H␈↓single␈αletters␈αsuch␈αas␈α␈↓↓x␈↓␈αor␈α␈↓↓u␈↓␈αare␈αused,␈α but␈αoccasionly␈αwe␈αuse␈αa␈αname␈αintended␈αto␈αsuggest␈αa␈αspecial
␈↓ ↓H␈↓subset␈α
of␈α
the␈α
S-expressions␈αas␈α
the␈α
intended␈α
range.␈α
 The␈αcorresponding␈α
internal␈α
form␈α
will␈α
be␈αthe
␈↓ ↓H␈↓atom␈α∞whose␈α∞name␈α∞is␈α∞the␈α∞same␈α∞identifier␈α∂but␈α∞in␈α∞upper␈α∞case␈α∞(and␈α∞appearing␈α∞in␈α∂the␈α∞S-expression
␈↓ ↓H␈↓font).␈α⊃ Thus␈α⊃␈↓¬X␈α⊃␈↓corresponds␈α⊃to␈α⊃␈↓↓x␈↓␈α⊃and␈α⊃␈↓¬U␈α⊃␈↓to␈α⊃␈↓↓u.␈↓␈α⊃ We␈α⊃will␈α⊃generally␈α⊃use␈α⊃␈↓↓x,␈↓␈α⊃␈↓↓y,␈↓␈α⊃␈↓↓z␈↓␈α⊃to␈α∩range␈α⊃over
␈↓ ↓H␈↓arbitrary S-expressions and ␈↓↓u,␈↓ ␈↓↓v,␈↓ ␈↓↓w␈↓ to range over lists.

␈↓ ↓H␈↓        Additional␈αterms␈α(called␈αapplication␈αterms)␈αcan␈αbe␈αformed␈αdenoting␈αthe␈αresult␈αof␈αone␈αof␈αthe
␈↓ ↓H␈↓basic␈α⊃LISP␈α⊂programs.␈α⊃These␈α⊃are␈α⊂expressed␈α⊃in␈α⊃external␈α⊂language␈α⊃using␈α⊃ordinary␈α⊂mathematical
␈↓ ↓H␈↓notation␈α∩for␈α⊃the␈α∩application␈α∩of␈α⊃functions␈α∩and␈α⊃predicates␈α∩to␈α∩a␈α⊃suitable␈α∩number␈α∩of␈α⊃arguments.
␈↓ ↓H␈↓Program␈α∀names␈α∀are␈α∃used␈α∀for␈α∀function␈α∀symbols␈α∃and␈α∀variables␈α∀or␈α∀S-expression␈α∃constants␈α∀as
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 98


␈↓ ↓H␈↓arguments.␈α⊗ Argument␈α⊗lists␈α⊗will␈α⊗be␈α⊗surrounded␈α⊗by␈α⊗``[]''␈α⊗thus␈α⊗reserving␈α⊗parentheses␈α⊗for␈α∃S-
␈↓ ↓H␈↓expressions.␈α
 The␈αbrackets␈α
will␈α
often␈αbe␈α
omitted␈αfor␈α
single␈α
arguments.␈α The␈α
internal␈α
notation␈αfor
␈↓ ↓H␈↓application␈α⊂terms␈α∂is␈α⊂more␈α∂uniform.␈α⊂ Namely␈α⊂such␈α∂an␈α⊂application␈α∂term␈α⊂is␈α∂represented␈α⊂by␈α⊂a␈α∂list,
␈↓ ↓H␈↓where␈α∩the␈α⊃first␈α∩element␈α⊃is␈α∩the␈α∩atom␈α⊃corresponding␈α∩to␈α⊃the␈α∩program␈α⊃name␈α∩and␈α∩the␈α⊃remaining
␈↓ ↓H␈↓elements of the list represent the arguments.

␈↓ ↓H␈↓        Table␈α∀1.␈α∪gives␈α∀some␈α∪examples␈α∀of␈α∀LISP␈α∪terms.␈α∀ Each␈α∪term␈α∀is␈α∪shown␈α∀in␈α∀external␈α∪and
␈↓ ↓H␈↓internal␈α
notation␈α
along␈α
with␈α
the␈α
S-expression␈α
value␈α
that␈α
it␈α
denotes.␈α
 Note␈α
that␈α
no␈αvariables␈α
appear
␈↓ ↓H␈↓in␈α
these␈α
examples␈α
because␈α∞the␈α
value␈α
denoted␈α
by␈α
a␈α∞LISP␈α
term␈α
containing␈α
a␈α
variable␈α∞depends␈α
on
␈↓ ↓H␈↓the value assigned to the variable.

␈↓ ↓H␈↓␈↓ α8External form␈↓ ∧xInternal form␈↓ 	xValue denoted

␈↓ ↓H␈↓␈↓ ↓H(i)␈↓ α8␈↓¬(A . B)␈↓␈↓ ∧x␈↓¬(QUOTE (A . B))␈↓␈↓ 	x␈↓¬(A . B)␈↓
␈↓ ↓H␈↓␈↓ α8␈↓¬(CAR  X)␈↓␈↓ ∧x␈↓¬(QUOTE (CAR  X))␈↓␈↓ 	x␈↓¬(CAR X)␈↓

␈↓ ↓H␈↓␈↓ ↓H(iia)␈↓ α8␈↓αa|␈↓␈↓¬(A . B)␈↓␈↓ ∧x␈↓¬(CAR (QUOTE (A . B)))␈↓␈↓ 	x␈↓¬A␈↓
␈↓ ↓H␈↓␈↓ ↓H(iid)␈↓ α8␈↓αd|␈↓␈↓¬(A . B)␈↓␈↓ ∧x␈↓¬(CDR (QUOTE (A . B)))␈↓␈↓ 	x␈↓¬B␈↓
␈↓ ↓H␈↓␈↓ ↓H(iic)␈↓ α8␈↓↓cons[␈↓¬A,B␈↓↓]␈↓␈↓ ∧x␈↓¬(CONS (QUOTE A) (QUOTE B))␈↓␈↓ 	x␈↓¬(A . B)␈↓

␈↓ ↓H␈↓␈↓ ↓H(iiia)␈↓ α8␈↓αa|␈↓␈↓¬((A . B) . A)␈↓␈↓ ∧x␈↓¬(CAR (QUOTE ((A . B) . A))␈↓␈↓ 	x␈↓¬(A . B)␈↓
␈↓ ↓H␈↓␈↓ ↓H(iiid)␈↓ α8␈↓αd|␈↓␈↓¬((A . B) . A)␈↓␈↓ ∧x␈↓¬(CDR (QUOTE ((A . B) . A))␈↓␈↓ 	x␈↓¬A␈↓
␈↓ ↓H␈↓␈↓ ↓H(iiic)␈↓ α8␈↓↓cons[␈↓¬(A . B),A␈↓↓]␈↓␈↓ ∧x␈↓¬(CONS (QUOTE (A . B)) (QUOTE A))␈↓␈↓ 	x␈↓¬((A . B) . A)␈↓

␈↓ ↓H␈↓␈↓ ↓H(iva)␈↓ α8␈↓αa|␈↓␈↓¬(A B C D)␈↓␈↓ ∧x␈↓¬(CAR (QUOTE (A B C D)))␈↓␈↓ 	x␈↓¬A␈↓
␈↓ ↓H␈↓␈↓ ↓H(ivd)␈↓ α8␈↓αd|␈↓␈↓¬(A B C D)␈↓␈↓ ∧x␈↓¬(CDR (QUOTE (A B C D)))␈↓␈↓ 	x␈↓¬(B C D)␈↓
␈↓ ↓H␈↓␈↓ ↓H(ivc)␈↓ α8␈↓↓cons[␈↓¬A,(B C D)␈↓↓]␈↓␈↓ ∧x␈↓¬(CONS (QUOTE A) (QUOTE (B C D)))␈↓␈↓ 	x␈↓¬(A B C D)␈↓

␈↓ ↓H␈↓␈↓ ↓H(v)␈↓ α8␈↓αat|␈↓␈↓¬A␈↓␈↓ ∧x␈↓¬(ATOM (QUOTE A))␈↓␈↓ 	x␈↓¬T␈↓
␈↓ ↓H␈↓␈↓ α8␈↓αat|␈↓␈↓¬(A . B)␈↓␈↓ ∧x␈↓¬(ATOM (QUOTE (A . B))␈↓␈↓ 	x␈↓¬NIL␈↓

␈↓ ↓H␈↓␈↓ ↓H(vi)␈↓ α8␈↓¬A␈↓ ␈↓αeq␈↓ ␈↓¬A␈↓␈↓ ∧x␈↓¬(EQ (QUOTE A) (QUOTE A))␈↓␈↓ 	x␈↓¬T␈↓
␈↓ ↓H␈↓␈↓ α8␈↓¬A␈↓ ␈↓αeq␈↓ ␈↓¬B␈↓␈↓ ∧x␈↓¬(EQ (QUOTE A) (QUOTE B))␈↓␈↓ 	x␈↓¬NIL␈↓
␈↓ ↓H␈↓␈↓ α8␈↓¬(A . B)␈↓ ␈↓αeq␈↓ ␈↓¬(A . B)␈↓␈↓ ∧x␈↓¬(EQ (QUOTE (A . B)) (QUOTE (A . B)))␈↓␈↓ 	x␈↓¬?␈↓



␈↓ ↓H␈↓␈↓ α∨␈↓αTable 1.␈↓  Examples of LISP terms in external and internal notation and their values.


␈↓ ↓H␈↓        We␈α⊂now␈α∂describe␈α⊂the␈α⊂basic␈α∂LISP␈α⊂programs␈α∂and␈α⊂give␈α⊂their␈α∂external␈α⊂and␈α⊂internal␈α∂names.
␈↓ ↓H␈↓The␈α
external␈α
names␈α∞are␈α
generally␈α
abbreviations␈α∞for␈α
the␈α
internal␈α
names␈α∞and␈α
will␈α
appear␈α∞in␈α
bold
␈↓ ↓H␈↓face type.

␈↓ ↓H␈↓        We␈α
begin␈αwith␈α
the␈α
programs␈αfor␈α
the␈α
selector␈αfunctions.␈α
 ␈↓↓car␈↓␈α
is␈αrepresented␈α
externally␈αby␈α
  ␈↓αa␈↓  
␈↓ ↓H␈↓and␈αinternally␈αby␈α␈↓¬CAR.␈α␈↓␈αWhen␈αapplied␈αto␈αa␈αnon-atomic␈αlist␈αstructure␈αthe␈αresult␈αis␈αthe␈αa-part.␈α See
␈↓ ↓H␈↓Table␈α1␈α(iia)␈αand␈α
(iiia)␈αfor␈αexamples.␈α ␈↓↓cdr␈↓␈α
is␈αrepresented␈αexternally␈αby␈α
  ␈↓αd␈↓  ␈αand␈αinternally␈αby␈α
␈↓¬CDR.
␈↓ ↓H␈↓¬␈↓ When␈αapplied␈αto␈αa␈αnon-atomic␈αlist␈αstructure␈αthe␈αresult␈αis␈αthe␈αd-part.␈α See␈αTable␈α1␈α(iid)␈αand␈α
(iiid).
␈↓ ↓H␈↓The␈α⊂action␈α⊂of␈α⊂the␈α⊂selector␈α⊂operations␈α⊂on␈α∂atoms␈α⊂is␈α⊂not␈α⊂defined␈α⊂in␈α⊂basic␈α⊂LISP.␈α⊂ However,␈α∂most
␈↓ ↓H␈↓implementations assign a some "meaning" to such terms, possibly an error message.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ 99


␈↓ ↓H␈↓        Since␈α∂lists␈α∞are␈α∂a␈α∂particular␈α∞kind␈α∂of␈α∂S-expression,␈α∞the␈α∂action␈α∂of␈α∞the␈α∂selector␈α∂operations␈α∞on
␈↓ ↓H␈↓non-empty␈α⊂lists␈α⊂is␈α∂also␈α⊂determined␈α⊂by␈α⊂the␈α∂above␈α⊂definitions.␈α⊂ In␈α∂particular␈α⊂ ␈↓αa␈↓ ␈α⊂selects␈α⊂the␈α∂first
␈↓ ↓H␈↓element␈α
of␈α∞the␈α
list␈α∞and␈α
 ␈↓αd␈↓ ␈α∞selects␈α
the␈α∞rest␈α
of␈α∞the␈α
list␈α∞(e.g.␈α
the␈α∞list␈α
formed␈α∞by␈α
removing␈α∞that␈α
first
␈↓ ↓H␈↓element).␈αSee␈αTable␈α1␈α(iva)␈α
and␈α(ivd).␈α Recall␈α that␈αthe␈αa-part␈α
of␈αa␈αnon-empty␈αlist␈αcan␈αbe␈α
any␈αS-
␈↓ ↓H␈↓expression,␈α⊃while␈α⊂the␈α⊃d-part␈α⊂is␈α⊃always␈α⊃a␈α⊂list.␈α⊃ Thus␈α⊂the␈α⊃selectors␈α⊂behave␈α⊃symmetrically␈α⊃on␈α⊂S-
␈↓ ↓H␈↓expressions␈α∂but␈α∂unsymmetrically␈α∂on␈α∂lists␈α∂reflecting␈α∂the␈α∂symmetry␈α∂properties␈α∂of␈α∂the␈α⊂list␈α∂structure
␈↓ ↓H␈↓representation of S-expressions and lists.

␈↓ ↓H␈↓[Historical␈αnote:␈αthe␈αnames␈α"CAR"␈αand␈α"CDR"␈αstood␈αfor␈α"contents␈αof␈αthe␈αaddress␈αpart␈αof␈αregister"
␈↓ ↓H␈↓and␈α∞"contents␈α∞of␈α∞the␈α∞decrement␈α∞part␈α∞of␈α∞register"␈α∞in␈α∞a␈α∞1957␈α∞precursor␈α∞of␈α∞LISP␈α∞projected␈α∞for␈α∞the
␈↓ ↓H␈↓IBM 704 computer.  The names have persisted for lack of a clearly preferable alternative.]

␈↓ ↓H␈↓        ␈↓↓cons␈↓␈αis␈α
represented␈αexternally␈αby␈α
␈↓αcons␈↓␈αor␈α(more␈α
often)␈αby␈αan␈α
infixed␈α`` . ''␈αand␈α
internally␈αby
␈↓ ↓H␈↓␈↓¬CONS.␈α
␈↓␈α
 The␈αprogram␈α
for␈α
␈↓↓cons␈↓␈αmust␈α
have␈α
access␈α
to␈αa␈α
supply␈α
of␈αcons-cells␈α
called␈α
the␈α
free␈αstorage
␈↓ ↓H␈↓list.␈α Given␈αpointers␈αto␈αtwo␈αexisting␈αlist␈αstructures,␈αthe␈αprogram␈αremoves␈αa␈αcons-cell␈αfrom␈αthe␈αfree
␈↓ ↓H␈↓storage␈αlist␈αand␈αputs␈αthe␈αfirst␈αpointer␈α(address)␈α
into␈αthe␈αa-part␈αand␈αthe␈αsecond␈αinto␈αthe␈α
d-part␈αof
␈↓ ↓H␈↓this␈α∂cell.␈α⊂ The␈α∂result␈α⊂is␈α∂the␈α⊂S-expression␈α∂represented␈α⊂by␈α∂the␈α⊂pointer␈α∂to␈α⊂the␈α∂new␈α⊂cons-cell.␈α∂ See
␈↓ ↓H␈↓Table 1 (iic) and (iiic).

␈↓ ↓H␈↓        We␈α
see␈α
that␈α
for␈α
lists,␈α ␈↓↓cons␈↓ ␈α
is␈α
a␈α
prefixing␈α
operation.␈α Namely,␈α
if␈α
the␈α
second␈α
argument␈α
is␈αa
␈↓ ↓H␈↓list␈α∞then␈α∞the␈α∂result␈α∞of␈α∞applying␈α∂␈↓↓cons␈↓␈α∞is␈α∞the␈α∞list␈α∂obtained␈α∞by␈α∞putting␈α∂the␈α∞first␈α∞argument␈α∂onto␈α∞the
␈↓ ↓H␈↓front of that list.  See Table 1 (ivc).

␈↓ ↓H␈↓[Note␈α
that␈α
giving␈αthe␈α
same␈α
pair␈αof␈α
pointers␈α
to␈αthe␈α
␈↓↓cons␈↓␈α
program␈αa␈α
second␈α
time␈αwill␈α
result␈α
in␈αthe
␈↓ ↓H␈↓construction␈α∩of␈α∪a␈α∩list␈α∩structure␈α∪distinct␈α∩from␈α∩the␈α∪first,␈α∩although␈α∩both␈α∪represent␈α∩the␈α∪same␈α∩S-
␈↓ ↓H␈↓expression.]

␈↓ ↓H␈↓        The␈αpredicate␈α
␈↓↓atom␈↓␈αis␈α
represented␈αexternally␈α
by␈α␈↓αat␈↓␈αand␈α
internally␈αby␈α
␈↓¬ATOM.␈α␈↓␈α
The␈αprogram
␈↓ ↓H␈↓for␈α␈↓↓atom␈↓␈αwhen␈αgiven␈αa␈αpointer␈αto␈αa␈αlist␈αstructure␈αdetermines␈αwhether␈αthat␈αlist␈αstructure␈αrepresents
␈↓ ↓H␈↓and␈αatom␈α
or␈αnot.␈αThe␈α
result␈αis␈α
␈↓¬T␈↓␈αif␈αthe␈α
list␈αstructure␈α
is␈αatomic␈αand␈α
␈↓¬NIL␈↓␈αotherwise.␈α
 See␈αTable␈α1␈α
(v).
␈↓ ↓H␈↓We␈α∂see␈α∂that␈α∂the␈α∂truthvalues␈α⊂␈↓αtrue␈↓␈α∂and␈α∂␈↓αfalse␈↓␈α∂are␈α∂represented␈α∂in␈α⊂LISP␈α∂by␈α∂the␈α∂atoms␈α∂␈↓¬T␈↓␈α⊂and␈α∂␈↓¬NIL␈↓
␈↓ ↓H␈↓respectively.

␈↓ ↓H␈↓        The␈α⊃predicate␈α∩␈↓↓eq␈↓␈α⊃is␈α∩represented␈α⊃externally␈α∩by␈α⊃the␈α∩infix␈α⊃␈↓αeq␈↓␈α∩and␈α⊃internally␈α∩by␈α⊃␈↓¬EQ.␈α∩␈↓␈α⊃As
␈↓ ↓H␈↓mentioned␈α
earlier,␈α
it␈α
is␈α
only␈α
required␈α
to␈α
test␈α
for␈α
equality␈α
of␈α
atoms.␈α
 The␈α
program␈α
for␈α∞␈↓↓eq␈↓␈α
actually
␈↓ ↓H␈↓does␈αa␈αbit␈αmore.␈α Namely,␈αgiven␈αpointers␈αto␈α
two␈αlist␈αstructures␈αit␈αcompares␈αthese␈αaddresses.␈α If␈α
they
␈↓ ↓H␈↓are␈α∂equal␈α∂the␈α∂result␈α∞is␈α∂␈↓¬T␈↓,␈α∂otherwise␈α∂it␈α∂is␈α∞␈↓¬NIL␈↓.␈α∂ Since␈α∂each␈α∂atom␈α∞is␈α∂represented␈α∂by␈α∂a␈α∂unique␈α∞list
␈↓ ↓H␈↓structure,␈α∞the␈α
comparison␈α∞is␈α
indeed␈α∞a␈α
test␈α∞of␈α
equality␈α∞if␈α
at␈α∞least␈α
one␈α∞of␈α
the␈α∞arguments␈α∞is␈α
atomic.
␈↓ ↓H␈↓More␈αgenerally␈αif␈αtwo␈αlist␈αstructures␈αhave␈αthe␈αsame␈αaddress,␈αthey␈αrepresent␈αthe␈αsame␈αS-expression.
␈↓ ↓H␈↓The␈αconverse␈αis␈αfalse␈αbecause␈αthere␈αis␈αno␈αguarantee␈αthat␈αthe␈αsame␈αS-expression␈αis␈αnot␈αrepresented
␈↓ ↓H␈↓by␈α
two␈α
different␈α
list␈αstructures.␈α
 (Two␈α
applications␈α
of␈α␈↓↓cons␈↓␈α
to␈α
a␈α
pair␈αof␈α
list␈α
structures␈α
in␈αmost␈α
LISPs
␈↓ ↓H␈↓will␈αresult␈αin␈αtwo␈αlist␈αstructures␈αrepresenting␈αthe␈αsame␈αS-expression,␈αbut␈αwith␈αdifferent␈αaddresses.)
␈↓ ↓H␈↓Equality␈α
of␈α
S-expressions␈α
is␈α
tested␈α
by␈α
a␈α
program␈α
based␈α
on␈α
 ␈↓↓eq␈↓␈α
which␈α
we␈α
will␈α
describe␈α
in␈α
a␈αlater
␈↓ ↓H␈↓section.␈α∂ If␈α∂this␈α∂program␈α∂were␈α∂used␈α∂instead␈α⊂of␈α∂␈↓↓eq␈↓␈α∂as␈α∂a␈α∂basic␈α∂function,␈α∂LISP␈α∂would␈α⊂be␈α∂logically
␈↓ ↓H␈↓simpler, but many programs would be slower.

␈↓ ↓H␈↓        This␈α∂concludes␈α∂the␈α∂description␈α∞of␈α∂the␈α∂basic␈α∂LISP␈α∞programs.␈α∂ To␈α∂conclude␈α∂the␈α∂section␈α∞we
␈↓ ↓H␈↓give some further notational extensions, conventions and abbreviations.

␈↓ ↓H␈↓        Besides␈α
the␈α
basic␈α
functions␈αof␈α
LISP,␈α
there␈α
will␈αbe␈α
user-defined␈α
functions.␈α
 We␈αhaven't␈α
given
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *10


␈↓ ↓H␈↓the␈α∞mechanism␈α
for␈α∞function␈α
definition␈α∞yet,␈α
but␈α∞suppose␈α
a␈α∞function␈α
␈↓↓subst␈↓␈α∞taking␈α∞three␈α
arguments
␈↓ ↓H␈↓has␈α→been␈α~defined.␈α→ It␈α→may␈α~be␈α→used␈α~in␈α→terms␈α→like␈α~ ␈↓↓subst[x,y,z]␈↓ ␈α→having␈α~internal␈α→form
␈↓ ↓H␈↓ ␈↓¬(SUBST X Y Z)␈↓.

␈↓ ↓H␈↓        As␈α∂in␈α∞other␈α∂programming␈α∞languages␈α∂and␈α∞in␈α∂mathematics␈α∞generally,␈α∂application␈α∂terms␈α∞can
␈↓ ↓H␈↓have␈α∞arbitrary␈α∞terms␈α∂as␈α∞arguments,␈α∞not␈α∂just␈α∞variables␈α∞and␈α∞constants.␈α∂ Thus␈α∞we␈α∞have␈α∂terms␈α∞like
␈↓ ↓H␈↓ ␈↓↓[subst[x,y,␈↓αa|␈↓↓z]␈α∂.␈α∂subst[x,y,␈↓αd|␈↓↓z]]␈↓ ␈α∂involving␈α∞a␈α∂user␈α∂defined␈α∂function␈α∞␈↓↓subst.␈↓␈α∂ Its␈α∂internal␈α∂form␈α∞is
␈↓ ↓H␈↓ ␈↓¬(CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))␈↓.

␈↓ ↓H␈↓        ␈↓αn|␈↓␈↓↓x␈↓␈α∞ is␈α∞an␈α∞abbreviation␈α∞for␈α∞ ␈↓↓x␈α∞␈↓αeq␈↓↓␈α∞␈↓¬NIL␈↓↓␈↓.␈α
 It␈α∞rates␈α∞a␈α∞special␈α∞notation␈α∞because␈α∞ ␈↓¬NIL␈↓ ␈α∞plays␈α
the
␈↓ ↓H␈↓same␈αrole␈αamong␈α
lists␈αthat␈αzero␈α
plays␈αamong␈αnumbers,␈αand␈α
list␈αvariables␈αoften␈α
have␈αto␈αbe␈αtested␈α
to
␈↓ ↓H␈↓see if their value is ␈↓¬NIL␈↓.  Its internal form is ␈↓¬(NULL X)␈↓.

␈↓ ↓H␈↓    The␈αnotation␈α ␈↓↓list[x1, x2, . . . ,xn]␈↓ ␈αis␈αused␈αto␈αdenote␈αthe␈αcomposition␈αof␈α␈↓↓cons␈↓'s␈αthat␈αforms␈αa
␈↓ ↓H␈↓list␈α∂from␈α∞its␈α∂elements.␈α∂ Thus␈α∞ ␈↓↓list[x, y, z]␈↓ ␈α∂denotes␈α∞ ␈↓↓cons[x, cons[y, cons[z, ␈↓¬NIL␈↓↓]]]␈↓ ␈α∂and␈α∂forms␈α∞a
␈↓ ↓H␈↓list␈α
of␈αthree␈α
elements␈αout␈α
of␈αthe␈α
quantities␈α
␈↓↓x,␈↓␈α␈↓↓y,␈↓␈α
and␈α␈↓↓z.␈↓␈α
 We␈αoften␈α
write␈α ␈↓↓<x, y, . . ., z>␈↓ ␈α
instead
␈↓ ↓H␈↓of␈α⊂ ␈↓↓list[x, y, . . . , z]␈↓ ␈α⊃when␈α⊂this␈α⊂will␈α⊃not␈α⊂cause␈α⊂confusion.␈α⊃ The␈α⊂experienced␈α⊃implementer␈α⊂of
␈↓ ↓H␈↓programming␈α∩languages␈α∪will␈α∩expect␈α∪that␈α∩since␈α∪␈↓↓list␈↓␈α∩has␈α∪a␈α∩variable␈α∪number␈α∩of␈α∪arguments,␈α∩its
␈↓ ↓H␈↓implementation␈αwill␈αpose␈αproblems.␈α That␈αis␈αindeed␈αtrue.␈α The␈αinternal␈αform␈αof␈α ␈↓↓<x, y, . . ., z>␈↓ 
␈↓ ↓H␈↓is  ␈↓¬(LIST X Y . . . Z)␈↓.

␈↓ ↓H␈↓        Compositions␈αof␈α␈↓αa␈↓␈αand␈α␈↓αd␈↓␈αare␈αwritten␈αby␈αconcatenating␈αthe␈αletters␈α␈↓αa␈↓␈αand␈α␈↓αd␈↓.␈α Thus,␈αit␈αis␈αeasily
␈↓ ↓H␈↓seen␈α
that␈α∞␈↓αad|␈↓␈↓↓u␈↓␈α
denotes␈α∞the␈α
second␈α∞element␈α
of␈α∞the␈α
list␈α∞␈↓↓u,␈↓␈α
and␈α∞␈↓αadd|␈↓␈↓↓u␈↓␈α
denotes␈α∞the␈α
third␈α∞element␈α
of
␈↓ ↓H␈↓that list.  The internal names of these functions are ␈↓¬CADR ␈↓and ␈↓¬CADDR ␈↓respectively.

␈↓ ↓H␈↓        In␈α
external␈α
language,␈α∞we␈α
often␈α
omit␈α∞brackets␈α
for␈α
functions␈α∞of␈α
one␈α
argument.␈α∞ Thus␈α
 ␈↓↓alt x␈↓ 
␈↓ ↓H␈↓stands␈α∞for␈α∞ ␈↓↓alt[x]␈↓, ␈α∞and␈α∞ ␈↓↓alt alt x␈↓ ␈α∞stands␈α∞for␈α∞ ␈↓↓alt[alt[x]]␈↓ .␈α∞ This␈α∞convention␈α∞was␈α∞also␈α∞used␈α∞in␈α∞the
␈↓ ↓H␈↓descriptions of ␈↓αa␈↓, ␈↓αd␈↓, ␈↓αat␈↓, and ␈↓αn␈↓.



␈↓ ↓H␈↓α␈↓ ε⊂Exercise

␈↓ ↓H␈↓1.  What is the value of ␈↓↓< ␈↓¬A ␈↓↓. ␈↓αa|␈↓↓␈↓¬(B . C)␈↓↓, ␈↓¬D ␈↓↓. ␈↓αd|␈↓↓␈↓¬(B . C)␈↓↓>␈↓?

␈↓ ↓H␈↓2.  What combinations of ␈↓αa␈↓ and ␈↓αd␈↓ select ␈↓¬(X Y)␈↓ and ␈↓¬(CONS X Y)␈↓ respectively from

␈↓ ↓H␈↓␈↓ βP␈↓↓␈↓¬((LAMBDA (X Y) (CONS X Y)) (QUOTE A) (QUOTE B))␈↓↓␈↓ 



␈↓ ↓H␈↓6.  ␈↓αConditional terms.␈↓


␈↓ ↓H␈↓        When␈α∩the␈α∩value␈α⊃of␈α∩a␈α∩function␈α∩depends␈α⊃on␈α∩whether␈α∩a␈α∩certain␈α⊃predicate␈α∩is␈α∩true␈α∩of␈α⊃the
␈↓ ↓H␈↓arguments,␈α∂conditional␈α∂terms␈α∂are␈α∂used␈α∂to␈α∂describe␈α∂the␈α∂function.␈α∂ In␈α∂external␈α∂language␈α⊂a␈α∂simple
␈↓ ↓H␈↓conditional term has the form

␈↓ ↓H␈↓6.1)␈↓ ¬/␈↓↓␈↓αif␈↓↓ p ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ b        ␈↓ 
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *11


␈↓ ↓H␈↓where␈α␈↓↓p␈↓␈αis␈αa␈αpropositional␈αterm␈αand␈α␈↓↓a␈↓␈αand␈α␈↓↓b␈↓␈αcan␈αbe␈αany␈αterms.␈α By␈αpropositional␈αterm␈αwe␈αmean␈αa
␈↓ ↓H␈↓term␈α∂whose␈α⊂value␈α∂represents␈α∂a␈α⊂truthvalue␈α∂(␈↓αtrue␈↓␈α⊂or␈α∂␈↓αfalse␈↓).␈α∂ A␈α⊂(program␈α∂computing␈α⊂a)␈α∂predicate
␈↓ ↓H␈↓applied␈αto␈αa␈α
list␈αof␈αarguments␈α
is␈αa␈αpropositional␈α
term.␈α We␈αwill␈α
explain␈αhow␈αto␈α
form␈αsuch␈αterms␈α
in
␈↓ ↓H␈↓general in the next section.

␈↓ ↓H␈↓The␈αconditional␈αterm␈α(6.1)␈αis␈αevaluated␈αas␈αfollows:␈α
first␈α ␈↓↓p␈↓␈α is␈αevaluated␈αand␈αdetermined␈αto␈αbe␈α
true
␈↓ ↓H␈↓or␈α
false.␈α
 If␈α␈↓↓p␈↓␈α
is␈α
true,␈αthen␈α
␈↓↓a␈↓␈α
is␈αevaluated␈α
and␈α
its␈αvalue␈α
is␈α
the␈αvalue␈α
of␈α
the␈αexpression.␈α
 If␈α
␈↓↓p␈↓␈αis␈α
false,
␈↓ ↓H␈↓then␈α␈↓↓b␈↓␈αis␈αevaluated␈αand␈αits␈αvalue␈αis␈αthe␈αvalue␈αof␈αthe␈αexpression.␈α Note␈αthat␈αif␈α␈↓↓p␈↓␈αis␈αtrue,␈α␈↓↓b␈↓␈αis␈αnever
␈↓ ↓H␈↓evaluated,␈αand␈αif␈α␈↓↓p␈↓␈αis␈αfalse,␈αthen␈α␈↓↓a␈↓␈αis␈αnever␈αevaluated.␈α The␈αimportance␈αof␈αthis␈αwill␈αbe␈αexplained
␈↓ ↓H␈↓later.

␈↓ ↓H␈↓        A␈α∞familiar␈α∂function␈α∞that␈α∞can␈α∂be␈α∞written␈α∞conveniently␈α∂using␈α∞conditional␈α∞expressions␈α∂is␈α∞the
␈↓ ↓H␈↓absolute value of a real number.  We have

␈↓ ↓H␈↓6.2)␈↓ ¬≤␈↓↓|x| = ␈↓αif␈↓↓ x<0 ␈↓αthen␈↓↓ -x ␈↓αelse␈↓↓ x␈↓. 

␈↓ ↓H␈↓[Remark:   The common mathematical notation for such definitions is

␈↓"␈↓ ↓H␈↓␈↓ ¬x␈↓π/␈↓  ␈↓↓x␈↓  if ␈↓↓x ≥ 0␈↓
␈↓"␈↓ ↓H␈↓␈↓ ¬_␈↓↓|x|␈↓ =␈↓ ¬x␈↓π[␈↓
␈↓"␈↓ ↓H␈↓␈↓ ¬x␈↓π\␈↓ ␈↓↓-x␈↓  otherwise,


␈↓ ↓H␈↓but the right hand side is not allowed to be part of another expression.]

␈↓ ↓H␈↓More generally a conditional term has the form

␈↓ ↓H␈↓6.3)␈↓ β↑␈↓↓␈↓αif␈↓↓ p ␈↓αthen␈↓↓ a ␈↓αelse␈↓↓ ␈↓αif␈↓↓ q ␈↓αthen␈↓↓ b . . .  ␈↓αelse␈↓↓ ␈↓αif␈↓↓ s ␈↓αthen␈↓↓ d ␈↓αelse␈↓↓ e␈↓. 

␈↓ ↓H␈↓There␈α∞can␈α∞be␈α∞any␈α∂number␈α∞of␈α∞clauses.␈α∞The␈α∞value␈α∂is␈α∞determined␈α∞by␈α∞evaluating␈α∂the␈α∞propositional
␈↓ ↓H␈↓terms␈α␈↓↓p,␈↓␈α␈↓↓q,␈↓␈αetc.␈αuntil␈αa␈αtrue␈αterm␈αis␈α
found,␈αthe␈αvalue␈αis␈αthen␈αthat␈αof␈αthe␈αterm␈αfollowing␈α
the␈αnext
␈↓ ↓H␈↓␈↓αthen␈↓.␈α If␈αnone␈αof␈αthe␈α
propositional␈αterms␈αis␈αtrue,␈αthen␈αthe␈α
value␈αis␈αthat␈αof␈αthe␈αterm␈α
following␈αthe
␈↓ ↓H␈↓last ␈↓αelse␈↓.

␈↓ ↓H␈↓        Figure␈α_8␈α→shows␈α_an␈α_example␈α→of␈α_a␈α_(numeric)␈α→function␈α_defined␈α_using␈α→a␈α_conditional
␈↓ ↓H␈↓expression.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *12






␈↓"␈↓ ↓H␈↓                                           (0,1)
␈↓"␈↓ ↓H␈↓                                         ≤'`≥
␈↓"␈↓ ↓H␈↓                                       ≤'    `≥
␈↓"␈↓ ↓H␈↓            ↑                        ≤'        `≥
␈↓"␈↓ ↓H␈↓            ~                      ≤'            `≥
␈↓"␈↓ ↓H␈↓     tri[x] ~     αααααααααααααααα'                `αααααααααααααααα
␈↓"␈↓ ↓H␈↓            ~                  (-1,0)            (1,0)
␈↓"␈↓ ↓H␈↓             ααα→
␈↓"␈↓ ↓H␈↓              x


␈↓"␈↓ ↓H␈↓␈↓ αr␈↓↓tri[x] = ␈↓αif␈↓↓ x<-1 ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x<0 ␈↓αthen␈↓↓ 1+x ␈↓αelse␈↓↓ ␈↓αif␈↓↓ x<1 ␈↓αthen␈↓↓ 1-x ␈↓αelse␈↓↓ 0␈↓.

␈↓ ↓H␈↓␈↓ ∧t␈↓αFigure 8.␈↓  The triangle function.



␈↓ ↓H␈↓        The conditional term in internal language has the form

␈↓ ↓H␈↓6.4)␈↓ ∧g␈↓↓␈↓¬(COND ␈↓↓(p1 e1) (p2 e2) ... (pn en)␈↓¬)␈↓↓␈↓ 

␈↓ ↓H␈↓with␈α
any␈α
number␈αof␈α
␈↓↓p-e␈↓␈α
pairs.␈α
 Its␈αvalue␈α
is␈α
determined␈α
by␈αevaluating␈α
the␈α
␈↓↓p␈↓'s␈α
successively␈αuntil␈α
one
␈↓ ↓H␈↓is␈αfound␈αwith␈α
a␈αvalue␈αcorresponding␈α
to␈α␈↓αtrue␈↓.␈α The␈αvalue␈α
of␈αthe␈αcorresponding␈α
␈↓↓e␈↓␈αis␈αthen␈α
taken␈αas
␈↓ ↓H␈↓the␈α
value␈α
of␈α
the␈α
conditional␈α
term.␈α
 If␈α
none␈α
of␈α
the␈α
␈↓↓p␈↓'s␈α
is␈α
true,␈α
then␈α
the␈α
value␈α
of␈α
the␈αconditional␈α
term
␈↓ ↓H␈↓is␈αundefined.␈α (In␈αsome␈αimplementations␈αthe␈αconditional␈αterm␈αis␈αgiven␈αa␈αdefault␈αvalue␈αsuch␈αas␈α
␈↓¬NIL␈↓
␈↓ ↓H␈↓if none of the ␈↓↓p␈↓'s are true.)  

␈↓ ↓H␈↓[Remark:␈α∪In␈α∩the␈α∪internal␈α∪form,␈α∩all␈α∪the␈α∩␈↓↓e␈↓'s␈α∪are␈α∪treated␈α∩the␈α∪same␈α∩which␈α∪makes␈α∪programs␈α∩for
␈↓ ↓H␈↓interpreting␈α
or␈α∞compiling␈α
conditional␈α∞expressions␈α
easier␈α∞to␈α
write.␈α∞ This␈α
is␈α∞another␈α
way␈α∞in␈α
which
␈↓ ↓H␈↓expressions in internal language are made in a more regular way than in external language.  ]

␈↓ ↓H␈↓        Conditional expressions may be compounded with functions to get terms like

␈↓ ↓H␈↓6.5)␈↓ ∧2␈↓↓␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ v ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u . append[␈↓αd|␈↓↓u, v]      ␈↓ 

␈↓ ↓H␈↓involving a yet to be defined function ␈↓↓append.␈↓  The internal form of this is

␈↓ ↓H␈↓6.6)␈↓ αy␈↓↓␈↓¬(COND ((NULL U) V) (T (CONS (CAR U) (APPEND (CDR U) V))))␈↓↓.␈↓ 

␈↓ ↓H␈↓One␈α
would␈αnormally␈α
have␈αexpected␈α
to␈αwrite␈α
␈↓¬(QUOTE␈α
T)␈↓,␈αbut␈α
there␈αis␈α
a␈αspecial␈α
convention␈α
that␈α␈↓¬T␈↓
␈↓ ↓H␈↓may␈α∂be␈α∂written␈α∂without␈α⊂␈↓¬QUOTE.␈α∂␈↓␈α∂This␈α∂convention␈α∂applies␈α⊂to␈α∂␈↓¬NIL␈↓␈α∂also.␈α∂ This␈α∂means␈α⊂that␈α∂these
␈↓ ↓H␈↓symbols␈αcannot␈αbe␈αused␈αas␈αvariables.␈α As␈α
mentioned␈αin␈αsection␈α␈↓π∞␈↓␈α5,␈α␈↓¬T␈↓␈αrepresents␈α
the␈αpropositional
␈↓ ↓H␈↓constant␈α∞␈↓αtrue␈↓,␈α∞i.e.␈α∞it␈α∞is␈α∞always␈α∞true␈α∞so␈α∞that␈α
it␈α∞is␈α∞impossible␈α∞to␈α∞"fall␈α∞off␈α∞the␈α∞end"␈α∞of␈α∞a␈α
conditional
␈↓ ↓H␈↓expression␈α∂with␈α∂␈↓¬T␈↓␈α⊂as␈α∂its␈α∂last␈α∂␈↓↓p.␈↓␈α⊂ It␈α∂is␈α∂the␈α∂translation␈α⊂into␈α∂internal␈α∂form␈α∂of␈α⊂the␈α∂final␈α∂␈↓αelse␈↓␈α⊂of␈α∂a
␈↓ ↓H␈↓conditional expression in external form.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *13


␈↓ ↓H␈↓7.  ␈↓αPropositional terms.␈↓


␈↓ ↓H␈↓        As␈α∃mentioned␈α∃in␈α∃the␈α∃previous␈α∃section,␈α∃propositional␈α∃terms␈α∃are␈α∃a␈α∃terms␈α∃whose␈α∃value
␈↓ ↓H␈↓represents␈αa␈αtruth␈αvalue.␈α The␈αsimplest␈αpropositional␈αterms␈αare␈αthe␈αconstants␈α␈↓¬T␈↓␈αand␈α␈↓¬NIL␈↓.␈α If␈α␈↓πf␈↓␈αis␈αa
␈↓ ↓H␈↓predicate␈αof␈αn-arguments␈αthen␈α␈↓↓␈↓πf␈↓↓[x1, . . . ,xn]␈↓␈αis␈αa␈αpropositional␈αterm.␈α Additional␈αpropositional
␈↓ ↓H␈↓terms␈α∃can␈α∃be␈α∃formed␈α∃by␈α∃combining␈α∃terms␈α∃already␈α∃formed␈α∃using␈α∃the␈α∃logical␈α⊗operations␈α∃of
␈↓ ↓H␈↓conjunction(␈↓αand␈↓),␈α
disjunction(␈↓αor␈↓)␈α
and␈α
negation(␈↓αnot␈↓).␈α
 Both␈α
␈↓αand␈↓␈α
and␈α
␈↓αor␈↓␈α
are␈α
associative,␈α
so␈α
we␈αcan
␈↓ ↓H␈↓write expressions like  ␈↓↓p1 ␈↓αand␈↓↓ p2 ␈↓αand␈↓↓ p3␈↓  without worrying about the grouping.

␈↓ ↓H␈↓        The␈α∩value␈α∪of␈α∩a␈α∩propositional␈α∪term␈α∩can␈α∩be␈α∪determined␈α∩using␈α∩the␈α∪truth␈α∩table␈α∪given␈α∩in
␈↓ ↓H␈↓Table 2.


␈↓ ↓H␈↓␈↓ αx␈↓¬T␈↓ ␈↓αand␈↓ ␈↓¬T␈↓  = ␈↓¬T␈↓␈↓ ¬x␈↓¬T␈↓ ␈↓αor␈↓ ␈↓¬T␈↓  = ␈↓¬T␈↓
␈↓ ↓H␈↓␈↓ αx␈↓¬T␈↓ ␈↓αand␈↓ ␈↓¬NIL␈↓ = ␈↓¬NIL␈↓␈↓ ¬x␈↓¬T␈↓ ␈↓αor␈↓ ␈↓¬NIL␈↓ = ␈↓¬T␈↓␈↓ λ8␈↓αnot␈↓ ␈↓¬T␈↓  = ␈↓¬NIL␈↓
␈↓ ↓H␈↓␈↓ αx␈↓¬NIL␈↓ ␈↓αand␈↓ ␈↓¬T␈↓  = ␈↓¬NIL␈↓␈↓ ¬x␈↓¬NIL␈↓ ␈↓αor␈↓ ␈↓¬T␈↓  = ␈↓¬T␈↓␈↓ λ8␈↓αnot␈↓ ␈↓¬NIL␈↓ = ␈↓¬T␈↓
␈↓ ↓H␈↓␈↓ αx␈↓¬NIL␈↓ ␈↓αand␈↓ ␈↓¬NIL␈↓ = ␈↓¬NIL␈↓␈↓ ¬x␈↓¬NIL␈↓ ␈↓αor␈↓ ␈↓¬NIL␈↓ = ␈↓¬NIL␈↓


␈↓ ↓H␈↓␈↓ ∧!␈↓αTable 2.␈↓  Truth table for propositional terms.


␈↓ ↓H␈↓        The evaluation of propositional terms is defined using conditional terms as follows:

␈↓ ↓H␈↓7.1)␈↓ ¬α␈↓↓p ␈↓αand␈↓↓ q = ␈↓αif␈↓↓ p ␈↓αthen␈↓↓ q ␈↓αelse␈↓↓ ␈↓¬NIL␈↓↓␈↓

␈↓ ↓H␈↓7.2)␈↓ ¬↔␈↓↓ p ␈↓αor␈↓↓ q = ␈↓αif␈↓↓ p ␈↓αthen␈↓↓ p ␈↓αelse␈↓↓ q␈↓

␈↓ ↓H␈↓7.3)␈↓ ¬¬␈↓↓  ␈↓αnot␈↓↓ p = ␈↓αif␈↓↓ p ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ ␈↓¬T␈↓↓␈↓


␈↓ ↓H␈↓The internal forms of these definitions are

␈↓ ↓H␈↓␈↓ ∧H␈↓↓␈↓¬(AND P Q) = (COND (P Q) (T NIL))␈↓↓␈↓
␈↓ ↓H␈↓␈↓ ∧H␈↓↓␈↓¬ (OR P Q) = (COND (P P) (T Q))  ␈↓↓␈↓
␈↓ ↓H␈↓␈↓ ∧H␈↓↓␈↓¬  (NOT P) = (COND (P NIL) (T T))␈↓↓␈↓


␈↓ ↓H␈↓Note␈α
that␈α
if␈α
␈↓↓p␈↓␈α
is␈α
false␈α
then␈α
 ␈↓↓p ␈↓αand␈↓↓ q = ␈↓¬NIL␈↓↓␈↓ ␈α
independent␈α
of␈α
the␈α
value␈α
of␈α
␈↓↓q,␈↓␈α
and␈α
likewise␈α
if␈α
␈↓↓p␈↓␈αis
␈↓ ↓H␈↓true,␈α
then␈α ␈↓↓p ␈↓αor␈↓↓ q = ␈↓¬T␈↓↓␈↓ ␈α
independent␈αof␈α
␈↓↓q.␈↓␈α If␈α
␈↓↓p␈↓␈αhas␈α
been␈αevaluated␈α
and␈αfound␈α
to␈αbe␈α
false,␈α
then␈α␈↓↓q␈↓
␈↓ ↓H␈↓does␈α∞not␈α∞have␈α∞to␈α∞be␈α∞evaluated␈α∞at␈α∞all␈α∞to␈α∂find␈α∞the␈α∞value␈α∞of␈α∞␈↓↓p ␈↓αand␈↓↓ q␈↓,␈α∞and,␈α∞in␈α∞fact,␈α∞LISP␈α∂does␈α∞not
␈↓ ↓H␈↓evaluate␈α⊃␈↓↓q␈↓␈α⊃in␈α⊃this␈α⊂case.␈α⊃ Similarly,␈α⊃␈↓↓q␈↓␈α⊃is␈α⊂not␈α⊃evaluated␈α⊃in␈α⊃evaluating␈α⊂␈↓↓p ␈↓αor␈↓↓ q␈↓␈α⊃if␈α⊃␈↓↓p␈↓␈α⊃is␈α⊃true.␈α⊂This
␈↓ ↓H␈↓procedure␈αis␈αin␈α
accordance␈αwith␈αthe␈αabove␈α
conditional␈αexpression␈αdescriptions␈αof␈α
these␈αoperators.
␈↓ ↓H␈↓The␈α∞importance␈α∞of␈α∞this␈α∂convention,␈α∞which␈α∞contrasts␈α∞with␈α∞that␈α∂of␈α∞ALGOL␈α∞60,␈α∞will␈α∂be␈α∞apparent
␈↓ ↓H␈↓later when we discuss recursive definitions of functions and predicates.

␈↓ ↓H␈↓        Propositional␈α
expressions␈α
can␈α
be␈α
combined␈α
with␈α
functions␈α
and␈α
conditional␈α
expressions␈α
to␈α
get
␈↓ ↓H␈↓terms like

␈↓ ↓H␈↓7.4)␈↓ ∧@␈↓↓␈↓αif␈↓↓ [␈↓αn|␈↓↓u ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓u] ␈↓αthen␈↓↓ u ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u . alt ␈↓αdd|␈↓↓u␈↓ 
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *14


␈↓ ↓H␈↓whose internal form is

␈↓ ↓H␈↓7.5)␈↓ ↓m␈↓↓␈↓¬  (COND ((OR (NULL U) (NULL (CDR U))) U) (T (CONS (CAR U) (ALT (CDDR U)))))␈↓↓␈↓. 

␈↓ ↓H␈↓        We␈αconclude␈αthis␈αsection␈αwith␈αa␈αcouple␈αremarks.␈α First,␈αthe␈αonly␈αS-expressions␈αthat␈αwe␈αhave
␈↓ ↓H␈↓said␈αrepresent␈αtruthvalues␈αare␈α␈↓¬T␈↓␈αand␈α␈↓¬NIL␈↓.␈α However,␈αmost␈αLISP␈αimplementations␈αregard␈αany␈αnon-
␈↓ ↓H␈↓␈↓¬NIL␈↓␈α∃S-expression␈α⊗as␈α∃representing␈α∃␈↓αtrue␈↓.␈α⊗ These␈α∃LISPs␈α∃do␈α⊗not␈α∃distinguish␈α⊗between␈α∃between
␈↓ ↓H␈↓propositional␈α⊃terms␈α⊃and␈α⊂more␈α⊃general␈α⊃terms.␈α⊂ Thus␈α⊃any␈α⊃term␈α⊂can␈α⊃appear␈α⊃in␈α⊂the␈α⊃␈↓↓p␈↓␈α⊃part␈α⊃of␈α⊂a
␈↓ ↓H␈↓conditional␈α∀term.␈α∪ Second,␈α∀most␈α∪LISP␈α∀implementations␈α∀allow␈α∪␈↓αand␈↓␈α∀and␈α∪␈↓αor␈↓␈α∀to␈α∀have␈α∪arbitrary
␈↓ ↓H␈↓numbers␈α⊃of␈α∩arguments.␈α⊃ Since␈α∩these␈α⊃operations␈α∩are␈α⊃associative,␈α∩this␈α⊃can␈α∩be␈α⊃viewed␈α∩as␈α⊃simply
␈↓ ↓H␈↓omitting parentheses as it won't matter how the arguments are grouped.



␈↓ ↓H␈↓8.  ␈↓αRecursive function definitions.␈↓


␈↓ ↓H␈↓        In␈α∞such␈α∞languages␈α
as␈α∞FORTRAN␈α∞and␈α
ALGOL,␈α∞computer␈α∞programs␈α
are␈α∞expressed␈α∞in␈α
the
␈↓ ↓H␈↓main␈α⊃as␈α⊃sequences␈α⊃of␈α⊃assignment␈α⊃statements␈α⊃and␈α⊃conditional␈α⊃␈↓αgo␈α⊃to␈↓'s.␈α⊃ In␈α⊃LISP,␈α⊃programs␈α⊃are
␈↓ ↓H␈↓mainly expressed in the form of recursively defined functions.  We begin with an example.

␈↓ ↓H␈↓        We␈αwant␈α
a␈αfunction␈α␈↓↓alt␈↓␈α
such␈αthat␈α␈↓↓alt u␈↓␈α
 gives␈αa␈α
list␈αwhose␈αelements␈α
are␈αalternate␈αelements␈α
of
␈↓ ↓H␈↓the list ␈↓↓u␈↓ beginning with the first.  For example we want

␈↓ ↓H␈↓␈↓ ∧}␈↓↓   alt ␈↓¬(A B C D E)␈↓↓ = ␈↓¬(A C E)␈↓↓␈↓,
␈↓ ↓H␈↓␈↓ ∧x␈↓↓ alt ␈↓¬((A B) (C D))␈↓↓ = ␈↓¬((A B))␈↓↓␈↓,
␈↓ ↓H␈↓␈↓ ¬!␈↓↓           alt ␈↓¬(A)␈↓↓ = ␈↓¬(A)␈↓↓,   ␈↓
␈↓ ↓H␈↓␈↓ ¬∂␈↓↓             alt ␈↓¬NIL␈↓↓ = ␈↓¬NIL␈↓↓.     ␈↓


␈↓ ↓H␈↓and in LISP we can define ␈↓↓alt␈↓ by the recursion equation

␈↓ ↓H␈↓8.1) ␈↓ ∧∃␈↓↓alt u ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓u ␈↓αthen␈↓↓ u ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u . alt ␈↓αdd|␈↓↓u␈↓. 

␈↓ ↓H␈↓In case you need a review of our precedence conventions, fully bracketed it looks like

␈↓ ↓H␈↓␈↓ β;␈↓↓alt[u] ← [␈↓αif␈↓↓ [␈↓αn|␈↓↓[u] ␈↓αor␈↓↓ ␈↓αn|␈↓↓[␈↓αd|␈↓↓[u]]] ␈↓αthen␈↓↓ u ␈↓αelse␈↓↓ [␈↓αa|␈↓↓[u] . alt[␈↓αdd|␈↓↓[u]]]]␈↓. 

␈↓ ↓H␈↓        The␈α⊃terms␈α∩appearing␈α⊃in␈α⊃the␈α∩recursion␈α⊃equation␈α⊃are␈α∩formed␈α⊃by␈α⊃the␈α∩methods␈α⊃previously
␈↓ ↓H␈↓discussed.␈α Notice␈αthat␈αthe␈αfunction␈α␈↓↓alt␈↓␈αoccurs␈αin␈αthe␈αright␈αhand␈αside␈αof␈αits␈αown␈αdefining␈αequation
␈↓ ↓H␈↓and␈αthat␈αwe␈αuse␈α"←"␈αinstead␈αof␈α"="␈α.␈α The␈αrecursion␈αequation␈αtells␈αus␈αthat␈α␈↓↓alt␈↓␈αis␈αa␈αfunction␈αof␈αone
␈↓ ↓H␈↓variable␈α∞␈↓↓u,␈↓␈α∞and␈α∞that␈α∞the␈α∞value␈α∞of␈α∞␈↓↓alt␈α∞u␈↓␈α∞for␈α∞some␈α∞particular␈α∞list␈α∞is␈α∞computed␈α∞by␈α∂evaluating␈α∞the
␈↓ ↓H␈↓right␈α
hand␈α
side␈α
of␈α
the␈αdefinition,␈α
substituting␈α
that␈α
list␈α
for␈α␈↓↓u␈↓␈α
whenever␈α
␈↓↓u␈↓␈α
is␈α
encountered␈α
and␈αre-
␈↓ ↓H␈↓evaluating␈αthe␈αright␈αhand␈αside␈αwith␈αa␈αnew␈α␈↓↓u␈↓␈αwhenever␈αa␈αterm␈α␈↓↓alt␈αe␈↓␈αis␈αencountered.␈α This␈αprocess
␈↓ ↓H␈↓is best illustrated by evaluating some expressions.

␈↓ ↓H␈↓        Consider␈α
evaluating␈α
␈↓↓alt ␈↓¬NIL␈↓↓␈↓.␈α
 We␈αdo␈α
it␈α
by␈α
evaluating␈α
the␈αexpression␈α
to␈α
the␈α
right␈α
of␈αthe␈α
 "←" 
␈↓ ↓H␈↓in␈α
(8.1)␈α
remembering␈α
that␈αthe␈α
variable␈α
␈↓↓u␈↓␈α
has␈α
the␈αvalue␈α
␈↓¬NIL␈↓.␈α
 A␈α
conditional␈α
expression␈αis␈α
evaluated
␈↓ ↓H␈↓by␈α∞first␈α∞evaluating␈α∂the␈α∞first␈α∞propositional␈α∂term␈α∞-␈α∞in␈α∞this␈α∂case␈α∞␈↓↓␈↓αn|␈↓↓u␈α∞␈↓αor␈↓↓␈α∂␈↓αn|␈↓↓␈↓αd|␈↓↓u␈↓.␈α∞This␈α∞expression␈α∂is␈α∞a
␈↓ ↓H␈↓disjunction␈α∂so␈α∂we␈α∂first␈α∂evaluate␈α∂the␈α∂first␈α∞disjunct,␈α∂namely␈α∂␈↓αn|␈↓␈↓↓u.␈↓␈α∂(Recall␈α∂the␈α∂convention␈α∂given␈α∞in
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *15


␈↓ ↓H␈↓section␈α␈↓π∞␈↓␈α7).␈α Since␈α ␈↓↓u␈α=␈α␈↓¬NIL␈↓↓␈↓,␈α ␈↓↓␈↓αn|␈↓↓u␈↓ ␈αis␈αtrue,␈αthe␈αdisjunction␈αis␈αtrue,␈αand␈αthe␈αvalue␈αof␈αthe␈αconditional
␈↓ ↓H␈↓expression␈αis␈αthe␈αvalue␈αof␈αthe␈αterm␈αafter␈αthe␈αfirst␈αtrue␈αpropositional␈αterm.␈αThis␈αterm␈αis␈α␈↓↓u,␈↓␈αand␈αits
␈↓ ↓H␈↓value␈α
is␈α␈↓¬NIL␈↓,␈α
so␈α
the␈αvalue␈α
of␈α ␈↓↓alt[␈↓¬NIL␈↓↓]␈↓ ␈α
is␈α
␈↓¬NIL␈↓.␈α Obeying␈α
the␈αrules␈α
about␈α
the␈αorder␈α
of␈αevaluation␈α
of
␈↓ ↓H␈↓terms␈α
in␈αconditional␈α
and␈αpropositional␈α
expressions␈αis␈α
important␈αin␈α
this␈αcase␈α
since␈αif␈α
we␈αdidn't␈α
obey
␈↓ ↓H␈↓these␈α∞rules,␈α∂we␈α∞might␈α∂find␈α∞ourselves␈α∂trying␈α∞to␈α∞evaluate␈α∂ ␈↓↓␈↓αn|␈↓↓␈↓αd|␈↓↓u␈↓ ␈α∞or␈α∂ ␈↓↓alt[␈↓αdd|␈↓↓u]␈↓,␈α∞and␈α∂since␈α∞␈↓↓u␈↓␈α∂is␈α∞␈↓¬NIL␈↓,
␈↓ ↓H␈↓neither␈α∞of␈α∞these␈α∞has␈α∞a␈α∞value.␈α∞ (An␈α∞attempt␈α∞to␈α∞evaluate␈α∞them␈α∞would␈α∞result␈α∞in␈α∞an␈α∞error␈α∞return␈α
in
␈↓ ↓H␈↓most LISPs.)

␈↓ ↓H␈↓        As␈α
a␈α
second␈α
example,␈α
consider␈α
 ␈↓↓alt ␈↓¬(A B)␈↓↓␈↓.␈α
 Since␈α
neither␈α
␈↓αn|␈↓␈↓↓u␈↓␈α
nor␈α
␈↓αn|␈↓␈↓αd|␈↓␈↓↓u␈↓␈α
is␈α
true␈α
in␈α
this␈αcase,
␈↓ ↓H␈↓the␈α
disjunction␈α
 ␈↓↓␈↓αn|␈↓↓u␈α␈↓αor␈↓↓␈α
␈↓αn|␈↓↓␈↓αd|␈↓↓u␈↓ ␈α
is␈αfalse␈α
and␈α
the␈α
value␈αof␈α
the␈α
expression␈αis␈α
the␈α
value␈αof␈α
 ␈↓↓␈↓αa|␈↓↓u . alt ␈↓αdd|␈↓↓u␈↓.
␈↓ ↓H␈↓␈↓αa|␈↓␈↓↓u␈↓␈α⊂has␈α⊂the␈α⊂value␈α⊂␈↓¬A,␈α⊂␈↓and␈α⊂␈↓αdd|␈↓␈↓↓u␈↓␈α⊂has␈α⊂the␈α∂value␈α⊂␈↓¬NIL␈↓,␈α⊂so␈α⊂we␈α⊂must␈α⊂now␈α⊂evaluate␈α⊂␈↓↓alt ␈↓¬NIL␈↓↓␈↓,␈α⊂and␈α∂we
␈↓ ↓H␈↓already␈αknow␈αthat␈αthis␈αis␈α␈↓¬NIL␈↓.␈α Therefore,␈αthe␈αvalue␈αof␈α ␈↓↓alt ␈↓¬(A B)␈↓↓␈↓ ␈αis␈αthat␈αof␈α ␈↓¬A . NIL␈↓ ␈αwhich␈αis
␈↓ ↓H␈↓ ␈↓¬(A)␈↓.

␈↓ ↓H␈↓        This evaluation is described by the following  sequence of equations:

␈↓ ↓H␈↓␈↓ αX␈↓↓alt ␈↓¬(A B)␈↓↓␈↓␈↓ βX␈↓↓= ␈↓αif␈↓↓ [␈↓αn|␈↓↓␈↓¬(A B)␈↓↓ ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓␈↓¬(A B)␈↓↓] ␈↓αthen␈↓↓ ␈↓¬(A B)␈↓↓  ␈↓αelse␈↓↓ ␈↓αa|␈↓↓␈↓¬(A B)␈↓↓ . alt[␈↓αdd|␈↓↓␈↓¬(A B)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓αif␈↓↓ [␈↓αfalse␈↓↓ ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓␈↓¬(A B)␈↓↓] ␈↓αthen␈↓↓ ␈↓¬(A B)␈↓↓ ␈↓αelse␈↓↓ ␈↓αa|␈↓↓␈↓¬(A B)␈↓↓ . alt[␈↓αdd|␈↓↓␈↓¬(A B)␈↓↓]      ␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓αif␈↓↓ ␈↓αfalse␈↓↓ ␈↓αthen␈↓↓ ␈↓¬(A B)␈↓↓ ␈↓αelse␈↓↓ ␈↓αa|␈↓↓␈↓¬(A B)␈↓↓ . alt[␈↓αdd|␈↓↓␈↓¬(A B)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓αa|␈↓↓␈↓¬(A B)␈↓↓ . alt[␈↓αdd|␈↓↓␈↓¬(A B)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓¬A ␈↓↓. alt[␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓¬A ␈↓↓. ␈↓αif␈↓↓ [␈↓αn|␈↓↓␈↓¬NIL␈↓↓ ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓␈↓¬NIL␈↓↓] ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓  ␈↓αelse␈↓↓ ␈↓αa|␈↓↓␈↓¬NIL␈↓↓ . alt[␈↓αdd|␈↓↓␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓¬A ␈↓↓. ␈↓αif␈↓↓ [␈↓αtrue␈↓↓ ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓␈↓¬NIL␈↓↓] ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓  ␈↓αelse␈↓↓ ␈↓αa|␈↓↓␈↓¬NIL␈↓↓ . alt[␈↓αdd|␈↓↓␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓¬A ␈↓↓. ␈↓αif␈↓↓ ␈↓αtrue␈↓↓ ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓  ␈↓αelse␈↓↓ ␈↓αa|␈↓↓␈↓¬NIL␈↓↓ . alt[␈↓αdd|␈↓↓␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓¬A ␈↓↓. ␈↓¬NIL␈↓↓␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓= ␈↓¬(A)␈↓↓␈↓.


␈↓ ↓H␈↓        This␈αis␈α
still␈αvery␈α
long-winded,␈αand␈αnow␈α
that␈αthe␈α
reader␈αunderstands␈α
the␈αorder␈αof␈α
evaluation
␈↓ ↓H␈↓of conditional and propositional expressions, we can proceed more briefly to evaluate

␈↓ ↓H␈↓␈↓ β(␈↓↓alt[␈↓¬(A B C D E)␈↓↓]␈↓␈↓ ¬_␈↓↓= ␈↓¬A ␈↓↓. alt[␈↓¬(C D E)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓¬A ␈↓↓. [␈↓¬C ␈↓↓. alt[␈↓¬(E)␈↓↓]]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓¬A ␈↓↓. [␈↓¬(C E)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓¬(A C E)␈↓↓␈↓.


␈↓ ↓H␈↓        Here␈αare␈αthree␈αmore␈αexamples␈αof␈αrecursive␈αfunctions␈αand␈αtheir␈αapplication.␈α We␈αdefine␈α␈↓↓last␈↓
␈↓ ↓H␈↓by

␈↓ ↓H␈↓8.2) ␈↓ ∧U␈↓↓last u ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓u ␈↓αthen␈↓↓ ␈↓αa|␈↓↓u ␈↓αelse␈↓↓ last ␈↓αd|␈↓↓u␈↓, 

␈↓ ↓H␈↓and we compute

␈↓ ↓H␈↓␈↓ βh␈↓↓last ␈↓¬(A B C)␈↓↓␈↓␈↓ ¬_␈↓↓= ␈↓αif␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓␈↓¬(A B C)␈↓↓ ␈↓αthen␈↓↓ ␈↓αa|␈↓↓␈↓¬(A B C)␈↓↓  ␈↓αelse␈↓↓ last ␈↓αd|␈↓↓␈↓¬(A B C)␈↓↓␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= last ␈↓¬(B C)␈↓↓␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= last ␈↓¬(C)␈↓↓␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓¬C␈↓↓␈↓.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *16


␈↓ ↓H␈↓Clearly␈α ␈↓↓last␈↓␈α computes␈αthe␈αlast␈αelement␈αof␈αa␈αlist.␈α ␈↓↓last ␈↓¬NIL␈↓↓␈↓␈αis␈αundefined␈αin␈αthe␈αLISP␈αlanguage;␈αthe
␈↓ ↓H␈↓result␈αof␈αtrying␈αto␈αcompute␈αit␈αmay␈αbe␈αan␈αerror␈αmessage␈αor␈αmay␈αbe␈αsome␈αrandom␈αresult␈αdepending
␈↓ ↓H␈↓on␈αthe␈αimplementation.␈α (A␈αheavy␈αduty␈αversion␈αof␈α␈↓↓last␈↓␈αwould␈αexplicitly␈αcall␈αa␈αfunction␈αcalled␈α␈↓↓error␈↓
␈↓ ↓H␈↓with a string expressing the complaint that the program had tried to compute ␈↓↓last␈↓ ␈↓¬NIL␈↓.)  

␈↓ ↓H␈↓        The function  ␈↓↓subst␈↓  is defined by

␈↓ ↓H␈↓8.3) ␈↓ α∂␈↓↓subst[x, y, z] ← ␈↓αif␈↓↓ ␈↓αat|␈↓↓z ␈↓αthen␈↓↓ [␈↓αif␈↓↓ z ␈↓αeq␈↓↓ y ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ z] ␈↓αelse␈↓↓ subst[x,y,␈↓αa|␈↓↓z] . subst[x,y,␈↓αd|␈↓↓z]␈↓. 

␈↓ ↓H␈↓We have

␈↓ ↓H␈↓␈↓ ↓x␈↓↓subst[␈↓¬(A.B), X, ((X.A).X)␈↓↓] ␈↓␈↓ ¬_␈↓↓= subst[␈↓¬(A.B), X, (X.A)␈↓↓] . subst[␈↓¬(A.B), X, X␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= [subst[␈↓¬(A.B), X, X␈↓↓] . subst[␈↓¬(A.B), X, A␈↓↓]] . ␈↓¬(A.B)␈↓↓␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= [[␈↓¬(A.B)␈↓↓].␈↓¬A␈↓↓].␈↓¬(A.B)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓¬(((A.B).A).(A.B))␈↓↓␈↓.


␈↓ ↓H␈↓␈↓↓subst␈↓␈αcomputes␈αthe␈αresult␈αof␈αsubstituting␈αthe␈αS-expression␈α␈↓↓x␈↓␈αfor␈αthe␈αatom␈α␈↓↓y␈↓␈αin␈αthe␈αS-expression␈α␈↓↓z.␈↓
␈↓ ↓H␈↓This operation is important in all kinds of symbolic computation.

␈↓ ↓H␈↓        The␈α∩function␈α∩␈↓↓append[u,v]␈↓␈α∩which␈α∩gives␈α∩the␈α∪concatenation␈α∩of␈α∩the␈α∩lists␈α∩␈↓↓u␈↓␈α∩and␈α∩␈↓↓v␈↓␈α∪is␈α∩also
␈↓ ↓H␈↓important.  It is also denoted by the infixed expression  ␈↓↓u * v␈↓.  For example we have

␈↓ ↓H␈↓␈↓ ∧3␈↓↓␈↓¬  (A B C)␈↓↓ * ␈↓¬(D E F)␈↓↓ = ␈↓¬(A B C D E F)␈↓↓,␈↓

␈↓ ↓H␈↓␈↓ ∧S␈↓↓␈↓¬NIL␈↓↓ * ␈↓¬(A B)␈↓↓ =␈↓¬(A B)␈↓↓ = ␈↓¬(A B)␈↓↓ * ␈↓¬NIL␈↓↓,␈↓

␈↓ ↓H␈↓and the formal definition

␈↓ ↓H␈↓8.4) ␈↓ ∧C␈↓↓u * v ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ v ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u . [␈↓αd|␈↓↓u] * v␈↓. 

␈↓ ↓H␈↓The␈α∞␈↓↓append␈↓␈α∞function␈α
is␈α∞machine␈α∞coded␈α
in␈α∞most␈α∞Lisp␈α
systems␈α∞in␈α∞a␈α
way␈α∞that␈α∞allows␈α∞an␈α
arbitrary
␈↓ ↓H␈↓number␈α∃of␈α∀arguments,␈α∃e.g.␈α∃ ␈↓¬(APPEND␈α∀(QUOTE␈α∃(A␈α∃B))␈α∀(QUOTE␈α∃(C␈α∃D))␈α∀(QUOTE␈α∃(E␈α∃F)))␈↓␈α∀is
␈↓ ↓H␈↓␈↓¬(A B C D E F)␈↓.␈α
 It␈αis␈α
convenient␈α
to␈αuse␈α
an␈α
infix␈αfor␈α
␈↓↓append␈↓␈α
because␈αit␈α
is␈α
associative,␈αi.e.␈α
 ␈↓↓u␈α
*␈α[v␈α
*
␈↓ ↓H␈↓↓w]␈α∞=␈α∞[u␈α∞*␈α
v]␈α∞*␈α∞w␈↓␈α∞so␈α∞we␈α
can␈α∞just␈α∞write␈α∞ ␈↓↓u␈α
*␈α∞v␈α∞*␈α∞w␈↓.␈α∞We␈α
often␈α∞use␈α∞infix␈α∞notation␈α∞for␈α
recursively
␈↓ ↓H␈↓defined functions when it is mathematically conventional or convenient.

␈↓ ↓H␈↓        The␈αpropositional␈αoperations␈α
can␈αalso␈αbe␈α
used␈αin␈αmaking␈α
recursive␈αdefinitions␈αsince␈αwe␈α
take
␈↓ ↓H␈↓advantage of the order of evaluation of constituents.  Thus, we define a predicate  ␈↓↓equal␈↓  by

␈↓ ↓H␈↓8.5) ␈↓ α*␈↓↓equal[x,y] ← x ␈↓αeq␈↓↓ y ␈↓αor␈↓↓ [␈↓αnot␈↓↓ ␈↓αat|␈↓↓x ␈↓αand␈↓↓ ␈↓αnot␈↓↓ ␈↓αat|␈↓↓y ␈↓αand␈↓↓  equal[␈↓αa|␈↓↓x,␈↓αa|␈↓↓y] ␈↓αand␈↓↓ equal[␈↓αd|␈↓↓x, ␈↓αd|␈↓↓y]]␈↓. 

␈↓ ↓H␈↓␈↓↓equal[x,y]␈↓␈αis␈αtrue␈αif␈αand␈αonly␈αif␈α␈↓↓x␈↓␈αand␈α␈↓↓y␈↓␈αare␈αthe␈αsame␈αS-expression,␈αand␈αthe␈αuse␈αof␈αthis␈αpredicate
␈↓ ↓H␈↓makes␈αup␈αfor␈αthe␈αfact␈αthat␈αthe␈αbasic␈αpredicate␈α␈↓αeq␈↓␈αis␈αguaranteed␈αto␈αtest␈αequality␈αonly␈αwhen␈αone␈αof
␈↓ ↓H␈↓the operands is known to be an atom.  We shall also use the infixes  ␈↓α=␈↓  and  ␈↓α≠␈↓.

␈↓ ↓H␈↓        Membership of an S-expression ␈↓↓x␈↓ in a list ␈↓↓u␈↓ is tested by

␈↓ ↓H␈↓8.6) ␈↓ βU␈↓↓member[x, u] ← ␈↓αnot␈↓↓ ␈↓αn|␈↓↓u ␈↓αand␈↓↓ [[x = ␈↓αa|␈↓↓u] ␈↓αor␈↓↓ member[x, ␈↓αd|␈↓↓u]]␈↓. 

␈↓ ↓H␈↓This relation is also denoted by ␈↓↓x ε u␈↓.  Here are some computations:
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *17



␈↓ ↓H␈↓␈↓ βλ␈↓↓member[␈↓¬B, ␈↓↓␈↓¬(A B)␈↓↓]␈↓␈↓ ¬_␈↓↓= ␈↓αnot␈↓↓ ␈↓αn|␈↓↓␈↓¬(A B)␈↓↓ ␈↓αand␈↓↓ [[␈↓¬B ␈↓↓= ␈↓αa|␈↓↓␈↓¬(A B)␈↓↓]  ␈↓αor␈↓↓ member[␈↓¬B, ␈↓↓␈↓αd|␈↓↓␈↓¬(A B)␈↓↓]]␈↓,
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= member[␈↓¬B, ␈↓↓␈↓¬(B)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓αtrue␈↓↓␈↓.


␈↓ ↓H␈↓        Sometimes␈α
a␈α
function␈α
is␈α
defined␈α
with␈α
the␈α
help␈α
of␈α
auxiliary␈α
functions.␈α
 Thus,␈α
the␈α
reverse␈α
of␈α
a
␈↓ ↓H␈↓list ␈↓↓u␈↓ , (e.g.  ␈↓↓reverse[␈↓¬(A B C D)␈↓↓] = ␈↓¬(D C B A)␈↓↓␈↓), is given by the pair of equations

␈↓ ↓H␈↓␈↓ ¬,␈↓↓reverse[u] ← rev[u, ␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓8.7)
␈↓ ↓H␈↓␈↓ ∧≥␈↓↓rev[u, v] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ v ␈↓αelse␈↓↓ rev[␈↓αd|␈↓↓u, [␈↓αa|␈↓↓u].v]␈↓.

␈↓ ↓H␈↓A computation is:

␈↓ ↓H␈↓␈↓ β8␈↓↓reverse[␈↓¬(A B C)␈↓↓]␈↓␈↓ ¬_␈↓↓= rev[␈↓¬(A B C)␈↓↓, ␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= rev[␈↓¬(B C), (A)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= rev[␈↓¬(C), (B A)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= rev[␈↓¬NIL␈↓↓, ␈↓¬(C B A)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓¬(C B A)␈↓↓␈↓.


␈↓ ↓H␈↓A more elaborate example of recursive definition is given by

␈↓ ↓H␈↓␈↓ βh␈↓↓flatten[x] ← flat[x, ␈↓¬NIL␈↓↓]                                       ␈↓
␈↓ ↓H␈↓8.8)
␈↓ ↓H␈↓␈↓ βd␈↓↓flat[x, u] ← ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ x.u ␈↓αelse␈↓↓ flat[␈↓αa|␈↓↓x, flat[␈↓αd|␈↓↓x, u]]␈↓.

␈↓ ↓H␈↓We have

␈↓ ↓H␈↓␈↓ αx␈↓↓flatten[␈↓¬((A.B).C)␈↓↓]␈↓␈↓ ¬_␈↓↓= flat[␈↓¬((A.B).C)␈↓↓, ␈↓¬NIL␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= flat[␈↓¬(A.B)␈↓↓, flat[␈↓¬C, ␈↓↓␈↓¬NIL␈↓↓]]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= flat[␈↓¬(A.B), (C)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= flat[␈↓¬A, ␈↓↓flat[␈↓¬B, (C)␈↓↓]]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= flat[␈↓¬A, (B C)␈↓↓]␈↓
␈↓ ↓H␈↓␈↓ ¬_␈↓↓= ␈↓¬(A B C)␈↓↓␈↓.


␈↓ ↓H␈↓The␈αreader␈αwill␈α
see␈αthat␈αthe␈αvalue␈α
of␈α␈↓↓flatten[x]␈↓␈αis␈αa␈α
list␈αof␈αthe␈αatoms␈α
of␈αthe␈αS-expression␈α
␈↓↓x␈↓␈αfrom
␈↓ ↓H␈↓left to right.  Thus ␈↓↓flatten[␈↓¬((A B) A)␈↓↓] = ␈↓¬(A B NIL A NIL)␈↓↓␈↓.

␈↓ ↓H␈↓        Many␈α⊃functions␈α⊃can␈α⊃be␈α∩conveniently␈α⊃written␈α⊃in␈α⊃more␈α∩than␈α⊃one␈α⊃way.␈α⊃ For␈α∩example,␈α⊃the
␈↓ ↓H␈↓function ␈↓↓reverse␈↓ mentioned above can be defined without an auxiliary function as follows:

␈↓ ↓H␈↓8.9) ␈↓ βn␈↓↓reverse1 u ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ reverse1 ␈↓αd|␈↓↓u * <␈↓αa|␈↓↓u>␈↓, 

␈↓ ↓H␈↓but␈α⊃the␈α⊂earlier␈α⊃definition␈α⊂involves␈α⊃less␈α⊂computation,␈α⊃because␈α⊂*␈α⊃takes␈α⊂time␈α⊃proportional␈α⊃to␈α⊂the
␈↓ ↓H␈↓length␈αof␈αits␈αfirst␈αargument.␈α Similarly␈αthe␈αfunction␈αcomputed␈αby␈α␈↓↓flatten␈↓␈αcan␈αalso␈αbe␈αcomputed␈αby
␈↓ ↓H␈↓the simpler but less efficient program ␈↓↓fringe␈↓

␈↓ ↓H␈↓8.10) ␈↓ βi␈↓↓fringe x ← ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ <x> ␈↓αelse␈↓↓ fringe ␈↓αa|␈↓↓x * fringe ␈↓αd|␈↓↓x␈↓, 
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *18


␈↓ ↓H␈↓        The␈α∪use␈α∪of␈α∪conditional␈α∪expressions␈α∪for␈α∪recursive␈α∪function␈α∪definition␈α∪is␈α∪not␈α∀limited␈α∪to
␈↓ ↓H␈↓functions␈α
of␈α
S-expressions.␈α For␈α
example,␈α
the␈αfactorial␈α
function␈α
and␈αthe␈α
Euclidean␈α
algorithm␈αfor
␈↓ ↓H␈↓the greatest common divisor on the non-negative integers may be written as follows:

␈↓ ↓H␈↓8.11) ␈↓ ∧t␈↓↓n! ← ␈↓αif␈↓↓ n=␈↓¬0 ␈↓↓␈↓αthen␈↓↓ ␈↓¬1 ␈↓↓␈↓αelse␈↓↓ n␈↓π*␈↓↓[n-␈↓¬1␈↓↓]!␈↓ 

␈↓ ↓H␈↓and

␈↓ ↓H␈↓8.12) ␈↓ αO␈↓↓gcd[m, n] ← ␈↓αif␈↓↓ m>n ␈↓αthen␈↓↓ gcd[n, m] ␈↓αelse␈↓↓ ␈↓αif␈↓↓ m=␈↓¬0 ␈↓↓␈↓αthen␈↓↓ n ␈↓αelse␈↓↓ gcd[n mod m, m]␈↓ 

␈↓ ↓H␈↓where␈α⊂␈↓↓n␈α⊂mod␈α⊂m␈↓␈α⊂denotes␈α⊂the␈α⊂remainder␈α⊂when␈α⊂␈↓↓n␈↓␈α⊂is␈α⊂divided␈α⊂by␈α⊂␈↓↓m␈↓␈α⊂and␈α⊂may␈α⊂itself␈α⊂be␈α⊂expressed
␈↓ ↓H␈↓recursively by

␈↓ ↓H␈↓8.13)␈↓ ∧)␈↓↓n mod m ← ␈↓αif␈↓↓ n<m ␈↓αthen␈↓↓ n ␈↓αelse␈↓↓ [n-m] mod m␈↓. 

␈↓ ↓H␈↓(Note␈α⊃that␈α⊃these␈α⊃definitions␈α⊃must␈α⊃be␈α⊃modified␈α⊃if␈α⊃negative␈α⊃integers␈α⊃are␈α⊃to␈α⊃be␈α⊃included␈α⊃in␈α⊃the
␈↓ ↓H␈↓domain.)

␈↓ ↓H␈↓        The␈αinternal␈αform␈αof␈αfunction␈αdefinitions␈αdepends␈αon␈αthe␈αimplementation.␈α MACLISP␈αuses
␈↓ ↓H␈↓the form

␈↓ ↓H␈↓␈↓ β-(␈↓¬DEFUN ␈↓<function name> <list of variables> <right hand side>).

␈↓ ↓H␈↓Stanford␈αLISP␈αand␈αUCI␈αLISP␈αfor␈αthe␈αPDP-10␈αcomputer␈αuse␈αthe␈αsame␈αform␈αwith␈α␈↓¬DE␈α␈↓␈αin␈αplace␈αof
␈↓ ↓H␈↓␈↓¬DEFUN. ␈↓ Thus in MACLISP the definition of ␈↓↓subst␈↓ is

␈↓ ↓H␈↓¬␈↓ α((DEFUN SUBST (X Y Z)
␈↓ ↓H␈↓¬␈↓ α(  (COND ((ATOM Z) (COND ((EQ Z Y) X) (T Z)))
␈↓ ↓H␈↓¬␈↓ α(        (T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z)))))),


␈↓ ↓H␈↓and the definition of ␈↓↓alt␈↓ is

␈↓ ↓H␈↓¬␈↓ αH(DEFUN ALT (U)
␈↓ ↓H␈↓¬␈↓ αH  (COND ((OR (NULL U) (NULL (CDR U))) U)
␈↓ ↓H␈↓¬␈↓ αH        (T (CONS (CAR U) (ALT (CDDR U)))))).


␈↓ ↓H␈↓Yet␈α
another␈α
notation␈α
for␈α
function␈α
definition␈αcalled␈α
the␈α
␈↓¬DEFPROP␈α
␈↓notation␈α
will␈α
be␈α
explained␈αafter
␈↓ ↓H␈↓λ-expressions have been introduced.


␈↓ ↓H␈↓α␈↓ ε
Exercises

␈↓ ↓H␈↓        1. Consider the function ␈↓↓drop␈↓ defined by

␈↓ ↓H␈↓␈↓ ∧⊃␈↓↓drop[u] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ <␈↓αa|␈↓↓u> . drop[␈↓αd|␈↓↓u]␈↓. 

␈↓ ↓H␈↓Compute␈α⊃(by␈α⊃hand)␈α⊃␈↓↓drop[␈↓¬(A␈α⊃B␈α⊃C)␈↓↓]␈↓.␈α⊃ What␈α∩does␈α⊃␈↓↓drop␈↓␈α⊃do␈α⊃to␈α⊃lists␈α⊃in␈α⊃general?␈α⊃  Write␈α∩␈↓↓drop␈↓␈α⊃in
␈↓ ↓H␈↓internal notation using ␈↓¬DEFUN. ␈↓

␈↓ ↓H␈↓        2. What does the function
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *19


␈↓ ↓H␈↓␈↓ ∧∞␈↓↓r2[u] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ reverse[␈↓αa|␈↓↓u] . r2[␈↓αd|␈↓↓u]␈↓ 

␈↓ ↓H␈↓do to lists of lists?  How about

␈↓ ↓H␈↓␈↓ ∧∞␈↓↓r3[x] ← ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ reverse[r4[x]]            ␈↓ 

␈↓ ↓H␈↓␈↓ ∧∩␈↓↓r4[u] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ r3[␈↓αa|␈↓↓u] . r4[␈↓αd|␈↓↓u]?    ␈↓ 

␈↓ ↓H␈↓        3. Compare

␈↓ ↓H␈↓␈↓ ∧ε␈↓↓r3'[x] ← ␈↓αif␈↓↓ ␈↓αat|␈↓↓x ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ <r3'[␈↓αd|␈↓↓x]> * <r3'[␈↓αa|␈↓↓x]>␈↓ 

␈↓ ↓H␈↓with the function ␈↓↓r3␈↓ of the preceding example.

␈↓ ↓H␈↓        4. Consider ␈↓↓r5␈↓ defined by

␈↓ ↓H␈↓␈↓ β∞␈↓↓r5[u] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓u ␈↓αthen␈↓↓ u  ␈↓αelse␈↓↓ [␈↓αa|␈↓↓r5[␈↓αd|␈↓↓u]] . r5[␈↓αa|␈↓↓u . r5[␈↓αd|␈↓↓r5[␈↓αd|␈↓↓u]]]␈↓. 

␈↓ ↓H␈↓Compute␈α␈↓↓r5[␈↓¬(A␈αB␈αC␈αD)␈↓↓]␈↓.␈α What␈αdoes␈α␈↓↓r5␈↓␈αdo?␈α  Needless␈αto␈αsay,␈αthis␈αis␈αnot␈αa␈αgood␈αway␈αof␈αcomputing
␈↓ ↓H␈↓this␈α⊂function␈α⊃even␈α⊂though␈α⊂it␈α⊃involves␈α⊂no␈α⊂auxiliary␈α⊃functions.␈α⊂ [This␈α⊂ingeneous␈α⊃definition␈α⊂was
␈↓ ↓H␈↓discovered by S. Ness]



␈↓ ↓H␈↓9.  ␈↓αNumerical computation.␈↓


␈↓ ↓H␈↓        Numerical␈α
calculation␈α
and␈α
symbolic␈α
calculation␈α
must␈α
often␈α
be␈α
combined,␈α
so␈α
LISP␈αprovides
␈↓ ↓H␈↓for␈α⊂numerical␈α⊂computation␈α⊂also.␈α⊂ (Numbers␈α⊂could␈α⊂be␈α⊂represented␈α⊂as␈α⊂lists␈α⊂of␈α⊂digits,␈α⊂but␈α⊂then␈α⊂it
␈↓ ↓H␈↓would␈α⊂be␈α⊂difficult␈α⊂to␈α⊂take␈α⊂proper␈α⊂advantage␈α⊂of␈α⊂machine␈α⊂instructions␈α⊂that␈α⊂work␈α⊂with␈α⊂numbers
␈↓ ↓H␈↓directly).␈α⊂ Since␈α⊂we␈α⊂need␈α⊂to␈α⊂include␈α⊂numbers␈α∂as␈α⊂parts␈α⊂of␈α⊂symbolic␈α⊂expressions,␈α⊂LISP␈α⊂has␈α∂both
␈↓ ↓H␈↓integer␈α
and␈α
floating␈αpoint␈α
numbers␈α
which␈α
are␈αregarded␈α
as␈α
atoms␈α
that␈αmay␈α
be␈α
included␈α
as␈αatoms␈α
in
␈↓ ↓H␈↓writing S-expressions.  Thus we have the lists:

␈↓ ↓H␈↓¬␈↓ ¬_(1 3 5)
␈↓ ↓H␈↓¬␈↓ ¬_(3.5 6.1 -7.2E9)
␈↓ ↓H␈↓¬␈↓ ¬_(PLUS X 1.3).


␈↓ ↓H␈↓The␈αfirst␈αis␈αa␈αlist␈αof␈α
integers,␈αthe␈αsecond␈αa␈αlist␈αof␈α
floating␈αpoint␈αnumbers,␈αand␈αthe␈αthird␈αa␈α
symbolic
␈↓ ↓H␈↓list␈α∂containing␈α∂both␈α∂numerical␈α∂and␈α∂non-numerical␈α∂atoms.␈α∂ Integers␈α∂are␈α∂written␈α⊂without␈α∂decimal
␈↓ ↓H␈↓points␈αwhich␈αare␈α
used␈αto␈αsignal␈α
floating␈αpoint␈αnumbers.␈α As␈α
in␈αFORTRAN,␈αthe␈α
letter␈αE␈αis␈αused␈α
to
␈↓ ↓H␈↓signal␈αthe␈αexponent␈αof␈αa␈αfloating␈αpoint␈αnumber␈αwhich␈αis␈αa␈αsigned␈αinteger.␈α The␈αsizes␈α
of␈αnumbers
␈↓ ↓H␈↓admitted␈αdepends␈αon␈αthe␈αimplementation.␈α When␈αa␈αdotted␈αpair,␈αsay␈α␈↓¬(1␈α.␈α2)␈↓␈αis␈αwanted,␈αthe␈αspaces
␈↓ ↓H␈↓around␈αthe␈αdot␈αdistinguish␈αit␈αfrom␈αthe␈αlist␈α␈↓¬(1.2)␈↓␈αwhose␈αsole␈αelement␈αis␈αthe␈αfloating␈αpoint␈αnumber
␈↓ ↓H␈↓1.2.

␈↓ ↓H␈↓        In␈α∞external␈α∞language␈α∞we␈α∞will␈α∞use␈α∞ordinary␈α∞mathematical␈α∞notation␈α∞for␈α∂numerical␈α∞functions.
␈↓ ↓H␈↓As␈α
an␈α
example␈α
of␈αa␈α
function␈α
combining␈α
numeric␈α
and␈αsymbolic␈α
calculation␈α
we␈α
have␈α
the␈αfunction
␈↓ ↓H␈↓giving the length of a list defined by
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *20


␈↓ ↓H␈↓9.1)␈↓ ∧.␈↓↓length u ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ 1 + length ␈↓αd|␈↓↓u␈↓. 

␈↓ ↓H␈↓The internal notation for numerical functions is shown in the following examples:

␈↓ ↓H␈↓␈↓ ¬_␈↓¬(PLUS X Y ... Z)␈↓ for ␈↓↓x+y+...+z␈↓,
␈↓ ↓H␈↓␈↓ ¬_␈↓¬(TIMES X ... Z)␈↓ for ␈↓↓xy...z␈↓,
␈↓ ↓H␈↓␈↓ ¬_␈↓¬(MINUS X)␈↓ for ␈↓↓-x␈↓,
␈↓ ↓H␈↓␈↓ ¬_␈↓¬(DIFFERENCE X Y)␈↓ for ␈↓↓x-y␈↓,
␈↓ ↓H␈↓␈↓ ¬_␈↓¬(QUOTIENT X Y)␈↓ for ␈↓↓x/y␈↓,
␈↓ ↓H␈↓␈↓ ¬_␈↓¬(POWER X Y)␈↓ for ␈↓↓x␈↓∧y␈↓.


␈↓ ↓H␈↓        Besides␈α
functions␈αof␈α
numbers␈α
we␈αneed␈α
predicates␈α
on␈αnumbers␈α
and␈α
the␈αusual␈α
=,␈α
<,␈α>,␈α
≤,␈αand␈α
≥
␈↓ ↓H␈↓are␈α∀used␈α∪with␈α∀the␈α∀internal␈α∪names␈α∀␈↓¬EQUAL,␈α∀␈↓␈↓¬LESSP,␈α∪␈↓␈↓¬GREATERP,␈α∀␈↓␈↓¬LESSEQP,␈α∀␈↓and␈α∪␈↓¬GREATEREQP,
␈↓ ↓H␈↓¬␈↓respectively.␈α
 Not␈αall␈α
are␈α
implemented␈αin␈α
all␈αLISP␈α
systems,␈α
but␈αof␈α
course␈αthe␈α
remaining␈α
ones␈αcan
␈↓ ↓H␈↓be defined.  An additional predicate, ␈↓↓numberp,␈↓ is used to distinguish numbers from other atoms.

␈↓ ↓H␈↓        Since␈α∂numbers␈α∂that␈α∂form␈α∂part␈α∂of␈α∂list␈α∂structures␈α∂must␈α∂be␈α∂represented␈α∂by␈α∂pointers␈α∂anyway,
␈↓ ↓H␈↓there␈α⊃is␈α∩room␈α⊃for␈α∩a␈α⊃flag␈α∩distinguishing␈α⊃floating␈α∩point␈α⊃numbers␈α∩and␈α⊃integers.␈α∩ Therefore,␈α⊃the
␈↓ ↓H␈↓arithmetic␈α⊃operations␈α⊂are␈α⊃programmed␈α⊂to␈α⊃treat␈α⊂types␈α⊃dynamically,␈α⊂i.e.␈α⊃a␈α⊂variable␈α⊃may␈α⊃take␈α⊂an
␈↓ ↓H␈↓integer␈αvalue␈αat␈α
one␈αstep␈αof␈αcomputation␈α
and␈αa␈αreal␈αvalue␈α
at␈αanother.␈α The␈α
subroutines␈αrealizing
␈↓ ↓H␈↓the arithmetic functions make the appropriate tests and create results of appropriate types.

␈↓ ↓H␈↓        It␈α_is␈α→worth␈α_remarking␈α→that␈α_including␈α_type␈α→flags␈α_in␈α→numbers␈α_would␈α→benefit␈α_many
␈↓ ↓H␈↓programming languages besides LISP and would not cost much in either storage or hardware.

␈↓ ↓H␈↓        Dynamic␈α⊂typing␈α⊂of␈α∂variables␈α⊂is␈α⊂slow␈α∂compared␈α⊂to␈α⊂direct␈α∂use␈α⊂of␈α⊂the␈α⊂machine's␈α∂arithmetic
␈↓ ↓H␈↓instructions,␈α⊗so␈α⊗that␈α⊗LISP␈α∃can␈α⊗be␈α⊗efficiently␈α⊗used␈α∃interpretively␈α⊗only␈α⊗when␈α⊗the␈α∃numerical
␈↓ ↓H␈↓calculations␈α
are␈αsmall␈α
or␈α
at␈αleast␈α
small␈αcompared␈α
to␈α
the␈αsymbolic␈α
calculations␈αin␈α
a␈α
problem.␈α The
␈↓ ↓H␈↓MACLISP␈α∩compiler␈α⊃NCOMPLR␈α∩is␈α⊃able␈α∩to␈α⊃generate␈α∩efficient␈α⊃arithmetic␈α∩code.␈α∩ In␈α⊃particular,
␈↓ ↓H␈↓variables␈αcan␈α
be␈αdeclared␈αto␈α
be␈αof␈αa␈α
fixed␈αnumerical␈α
type␈αand␈αthe␈α
correct␈αmachine␈αinstructions␈α
are
␈↓ ↓H␈↓then␈α⊂generated␈α⊃so␈α⊂that␈α⊃runtime␈α⊂testing␈α⊂is␈α⊃not␈α⊂necessary.␈α⊃ Also,␈α⊂it␈α⊂uses␈α⊃separate␈α⊂stacks␈α⊃to␈α⊂store
␈↓ ↓H␈↓numerical␈αresults␈αso␈αthat␈αunecessary␈αconversion␈αfrom␈αthe␈αLISP␈αrepresentation␈αof␈αa␈αnumber␈αto␈αthe
␈↓ ↓H␈↓machine␈αrepresentation␈αcan␈αbe␈αavoided.␈α This␈αsaves␈αboth␈αtime␈αand␈αspace␈αas␈αeach␈αconversion␈αfrom
␈↓ ↓H␈↓a machine number to a LISP number requires a ␈↓↓cons␈↓ operation.

␈↓ ↓H␈↓        LISP␈α
can␈α
also␈α
deal␈α
with␈α
integers␈α
too␈α
large␈α
to␈α
be␈α
represented␈α
as␈α
a␈α
single␈α
machine␈α
word.␈α
 Such
␈↓ ↓H␈↓numbers␈α
are␈α∞called␈α
"bignums"␈α∞and␈α
are␈α∞repsented␈α
in␈α
LISP␈α∞by␈α
a␈α∞pointer␈α
to␈α∞a␈α
list␈α∞structure␈α
which
␈↓ ↓H␈↓contains␈αthe␈αsign,␈α
a␈αflag␈αsaying␈αthat␈α
this␈αa␈α"bignum",␈α
and␈αa␈αlist␈αof␈α
the␈αnumbers␈αcorresponding␈αto␈α
a
␈↓ ↓H␈↓base␈α∪B␈α∩representation␈α∪of␈α∩the␈α∪number␈α∩for␈α∪some␈α∩suitable␈α∪B␈α∩(depending␈α∪on␈α∩the␈α∪machine␈α∩and
␈↓ ↓H␈↓implementation).

␈↓ ↓H␈↓        As␈α∃another␈α∀example␈α∃of␈α∀a␈α∃combined␈α∀numeric␈α∃and␈α∀symbolic␈α∃computation,␈α∀we␈α∃give␈α∀an
␈↓ ↓H␈↓evaluator␈α⊂for␈α⊂expressions␈α⊂with␈α⊂sums␈α⊂and␈α⊃products.␈α⊂ The␈α⊂expressions␈α⊂are␈α⊂built␈α⊂up␈α⊃from␈α⊂atoms
␈↓ ↓H␈↓denoting variables and integer constants according to the syntax

␈↓ ↓H␈↓                <expression> ::= <variable> | <integer> | (␈↓¬PLUS ␈↓<explist>) | (␈↓¬TIMES ␈↓<explist>)
␈↓ ↓H␈↓9.2)
␈↓ ↓H␈↓                     <explist> ::= <expression> | <expression><explist>
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *21


␈↓ ↓H␈↓Thus␈αa␈αlist␈αof␈αexpressions␈αbeginning␈αwith␈αthe␈αatom␈α␈↓¬PLUS␈α␈↓represents␈αthe␈αsum␈αof␈αthese␈αexpressions
␈↓ ↓H␈↓and␈α∀a␈α∀list␈α∀of␈α∀expressions␈α∀beginning␈α∀with␈α∀the␈α∀atom␈α∀␈↓¬TIMES␈α∀␈↓represents␈α∀the␈α∀product␈α∃of␈α∀these
␈↓ ↓H␈↓expressions.␈α In␈αorder␈αto␈αevaluate␈αan␈αexpression␈α
we␈αneed␈αa␈αway␈αof␈αgiving␈αvalues␈αto␈α
the␈αvariables
␈↓ ↓H␈↓occuring␈α
in␈αthe␈α
expression.␈α  We␈α
will␈αuse␈α
an␈α␈↓↓association␈↓␈α
␈↓↓list␈↓␈αfor␈α
this␈αpurpose.␈α
 An␈α
association␈αlist
␈↓ ↓H␈↓(a-list)␈α
is␈α
a␈α∞list␈α
of␈α
pairs,␈α∞in␈α
our␈α
case␈α∞the␈α
first␈α
element␈α
of␈α∞each␈α
pair␈α
is␈α∞a␈α
variable␈α
and␈α∞the␈α
second
␈↓ ↓H␈↓element␈α
is␈α
the␈α
value␈α
associated␈αwith␈α
it.␈α
 For␈α
example␈α
 ␈↓¬((X␈α.␈α
5)␈α
(Y␈α
.␈α
9.3)␈α(Z␈α
.␈α
2.1))␈↓␈α
is␈α
an␈αa-
␈↓ ↓H␈↓list.␈α To␈αlook␈αup␈αthe␈αvalue␈αof␈αa␈αvariable␈αin␈αan␈αa-list␈αwe␈αuse␈αthe␈αfunction␈α␈↓↓assoc,␈↓␈αwhich␈αreturns␈αthe
␈↓ ↓H␈↓first␈α
pair␈α
in␈α
the␈α
list␈α
such␈α
that␈α
the␈α
variable␈α
matches␈α
the␈α
variable␈α
argument.␈α
 It␈α
returns␈α
␈↓¬NIL␈↓␈α
if␈αno
␈↓ ↓H␈↓value is found.  Thus

␈↓ ↓H␈↓␈↓ βG␈↓↓assoc[␈↓¬Y␈↓↓, ␈↓¬((X . 5) (Y . 9.3) (Z . 2.1))␈↓↓] = ␈↓¬(Y . 9.3)␈↓↓␈↓ 

␈↓ ↓H␈↓and the definition of ␈↓↓assoc␈↓ is given by

␈↓ ↓H␈↓9.3) ␈↓ α{␈↓↓assoc[x,a] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓a ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αaa|␈↓↓a ␈↓αeq␈↓↓ x ␈↓αthen␈↓↓ ␈↓αa|␈↓↓a ␈↓αelse␈↓↓ assoc[x,␈↓αd|␈↓↓a].␈↓ 

␈↓ ↓H␈↓Association␈αlists␈αare␈αgenerally␈αuseful␈αfor␈αassociating␈α"values"␈αwith␈α"symbols"␈αand␈αthey␈α
will␈αappear
␈↓ ↓H␈↓in␈α
many␈α∞later␈α
examples.␈α∞ We␈α
note␈α∞here␈α
two␈α∞features␈α
which␈α∞are␈α
due␈α∞to␈α
the␈α∞way␈α
␈↓↓assoc␈↓␈α∞is␈α
defined.
␈↓ ↓H␈↓Since␈α␈↓↓assoc␈↓␈αreturns␈αthe␈αpair␈αrather␈αthan␈αthe␈αvalue␈αwhen␈αthe␈αdesired␈αsymbol␈αis␈αfound␈αor␈α␈↓¬NIL␈↓␈αif␈αno
␈↓ ↓H␈↓value␈αis␈αfound,␈αthe␈αcase␈αof␈αno␈αvalue␈αfound␈αcan␈αbe␈αdetected.␈α If␈αjust␈αthe␈αvalue␈αwere␈αreturned␈αthere
␈↓ ↓H␈↓would␈α
be␈α
no␈α
distinction␈α
between␈αno␈α
value␈α
and␈α
a␈α
value␈α
of␈α␈↓¬NIL␈↓.␈α
 The␈α
calling␈α
program␈α
must␈αcheck␈α
to
␈↓ ↓H␈↓see␈α∂if␈α∂a␈α∂value␈α∞was␈α∂returned␈α∂(␈↓↓␈↓αnot␈↓↓␈α∂␈↓αn|␈↓↓assoc[x,a]␈↓)␈α∂and␈α∞then␈α∂extract␈α∂that␈α∂value␈α∂(␈↓↓␈↓αd|␈↓↓assoc[x,a]␈↓).␈α∞ Also,
␈↓ ↓H␈↓␈↓↓assoc␈↓␈αreturns␈αthe␈αfirst␈αpair␈αit␈αfinds,␈αthus␈αa␈αsymbol␈αcan␈αbe␈αassociated␈αwith␈αseveral␈αvalues␈αin␈αthe␈αa-
␈↓ ↓H␈↓list, but always the first occurence determines the result that is returned.   Thus

␈↓ ↓H␈↓␈↓ α1␈↓↓assoc[␈↓¬X␈↓↓,␈↓¬((U . 1.41) (X . 5) (Y . 9.3) (X . 1.2) (Z . 2.1))␈↓↓] = ␈↓¬(X . 5)␈↓↓␈↓. 

␈↓ ↓H␈↓␈↓↓assoc␈↓ is built into most LISP systems.

␈↓ ↓H␈↓        The interpreter, ␈↓↓numval,␈↓ can now be defined.

␈↓ ↓H␈↓␈↓ αx␈↓↓numval[e,a]␈↓␈↓ ∧8␈↓↓← ␈↓αif␈↓↓ numberp e ␈↓αthen␈↓↓ e␈↓
␈↓ ↓H␈↓␈↓ ∧8␈↓↓  ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat|␈↓↓e ␈↓αthen␈↓↓ ␈↓αd|␈↓↓assoc[e,a]␈↓
␈↓ ↓H␈↓9.4)␈↓ ∧8␈↓↓  ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e ␈↓αeq␈↓↓ ␈↓¬PLUS ␈↓↓␈↓αthen␈↓↓ evplus[␈↓αd|␈↓↓e,a]␈↓
␈↓ ↓H␈↓␈↓ ∧8␈↓↓  ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e ␈↓αeq␈↓↓ ␈↓¬TIMES ␈↓↓␈↓αthen␈↓↓ evtimes[␈↓αd|␈↓↓e,a]␈↓

␈↓ ↓H␈↓where

␈↓ ↓H␈↓9.5) ␈↓ αJ␈↓↓ evplus[u,a] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ 0 ␈↓αelse␈↓↓ numval[␈↓αa|␈↓↓u,a] + evplus[␈↓αd|␈↓↓u,a],                  ␈↓

␈↓ ↓H␈↓9.6) ␈↓ αb␈↓↓evtimes[u,a] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ numval[␈↓αa|␈↓↓u,a] ␈↓π*␈↓↓ evtimes[␈↓αd|␈↓↓u,a],             ␈↓





␈↓ ↓H␈↓10.  ␈↓αBitwise Boolean Operations␈↓


␈↓ ↓H␈↓        Besides␈αthe␈α
usual␈αarithmetic␈α
operations␈αon␈α
numbers,␈αLISP␈α
allows␈αbitwise␈αboolean␈α
operations
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *22


␈↓ ↓H␈↓on␈αwords␈αin␈αmemory.␈α Letting␈α␈↓↓m,␈↓␈αand␈α␈↓↓n␈↓␈αbe␈αstrings␈αof␈α␈↓¬1␈↓s␈αand␈α␈↓¬0␈↓s␈αof␈αsome␈αfixed␈α
length␈αdepending
␈↓ ↓H␈↓on␈αthe␈αmachine␈αword␈αsize,␈αthen␈α␈↓↓m␈α␈↓αbool-op␈↓↓␈αn␈↓␈αdenotes␈αthe␈αword␈αwhose␈αbinary␈αrepsentation␈αis␈αgiven
␈↓ ↓H␈↓by performing the boolean operation on each pair of corresponding bits.  Thus we have

␈↓ ↓H␈↓␈↓ ¬O␈↓¬4 ␈↓αbool-and␈↓¬ 6 = 4␈↓
␈↓ ↓H␈↓␈↓ ¬R␈↓¬ 4 ␈↓αbool-or␈↓¬ 6 = 6␈↓
␈↓ ↓H␈↓␈↓ ¬P␈↓¬4 ␈↓αbool-xor␈↓¬ 6 = 2␈↓

␈↓ ↓H␈↓Here␈α⊂␈↓αbool-xor␈↓␈α⊂is␈α⊃the␈α⊂exclusive␈α⊂or␈α⊃operation.␈α⊂ In␈α⊂general␈α⊂we␈α⊃will␈α⊂use␈α⊂terminology␈α⊃obtained␈α⊂by
␈↓ ↓H␈↓prefixing ␈↓αbool-␈↓ to the usual name of the corresponding logical operation for a boolean operation.

␈↓ ↓H␈↓        The␈α
internal␈α
form␈αfor␈α
boolean␈α
operations␈αon␈α
words␈α
has␈α
not␈αbeen␈α
standardized,␈α
but␈αthe␈α
form
␈↓ ↓H␈↓used by MACLISP is

␈↓ ↓H␈↓␈↓ ¬_(␈↓¬BOOLE ␈↓<code> <n1> <n2>)

␈↓ ↓H␈↓where␈α<code>␈αranges␈αfrom␈α␈↓¬0␈α␈↓to␈α␈↓¬15␈α␈↓(decimal)␈αand␈αeach␈αvalue␈αof␈α<code>␈αcorresponds␈αto␈αa␈αdifferent
␈↓ ↓H␈↓boolean␈α
operation.␈αWe␈α
have␈α
the␈αfollowing␈α
simple␈α
rule␈αfor␈α
determining␈α
what␈αoperation␈α
corresponds
␈↓ ↓H␈↓to␈α
a␈α
particular␈α
value␈α
of␈α
<code>.␈α
 If␈α
the␈αbinary␈α
representation␈α
of␈α
<code>␈α
is␈α
"␈↓¬abcd␈↓"␈α
then␈α
result␈αof␈α
the
␈↓ ↓H␈↓operation on a pair of bits ␈↓¬x ␈↓and ␈↓¬y ␈↓is given in table 3.

␈↓ ↓H␈↓¬␈↓ ∧8x␈↓ ∧xy␈↓ ¬x(BOOLE "abcd" x y)

␈↓ ↓H␈↓¬␈↓ ∧80␈↓ ∧x0␈↓ π_a
␈↓ ↓H␈↓¬␈↓ ∧80␈↓ ∧x1␈↓ π_c
␈↓ ↓H␈↓¬␈↓ ∧81␈↓ ∧x0␈↓ π_b
␈↓ ↓H␈↓¬␈↓ ∧81␈↓ ∧x1␈↓ π_d



␈↓ ↓H␈↓¬␈↓ ∧J␈↓αTable 3.␈↓¬  ␈↓Boolean operation encoding.␈↓¬


␈↓ ↓H␈↓In␈α∂particular␈α∂if␈α∂<code>␈α∂is␈α∂␈↓¬0␈α∂␈↓we␈α∂have␈α∂the␈α∂identically␈α∂␈↓¬0␈α∂␈↓operation,␈α∂if␈α∂<code>␈α∂is␈α∂␈↓¬15␈α∂␈↓we␈α⊂have␈α∂the
␈↓ ↓H␈↓identically␈α∞␈↓¬1␈α∞␈↓operation,␈α∞if␈α
<code>␈α∞is␈α∞␈↓¬1␈α∞␈↓we␈α
have␈α∞ ␈↓αbool-and␈↓,␈α∞and␈α∞if␈α
<code>␈α∞is␈α∞␈↓¬7␈α∞␈↓we␈α∞have␈α
 ␈↓αbool-or␈↓.
␈↓ ↓H␈↓Note that all 16 boolean functions of two variables are realized by the LISP ␈↓¬BOOLE ␈↓operation.

␈↓ ↓H␈↓        In␈α∞addition␈α
to␈α∞the␈α
above␈α∞operations␈α
LISP␈α∞has␈α
a␈α∞shift␈α
operation␈α∞␈↓↓lsh[n,d]␈↓␈α
which␈α∞shifts␈α
the
␈↓ ↓H␈↓bits␈α⊂of␈α⊂the␈α∂binary␈α⊂representation␈α⊂of␈α∂␈↓↓n,␈↓␈α⊂␈↓↓d␈↓␈α⊂positions␈α∂to␈α⊂the␈α⊂left,␈α∂filling␈α⊂the␈α⊂vacated␈α⊂spaces␈α∂with
␈↓ ↓H␈↓zeroes.␈α If␈α␈↓↓d␈↓␈αis␈αnegative␈αthe␈αshifting␈αis␈αto␈αthe␈αright␈αinstead.␈α The␈αinternal␈αform␈αof␈αthis␈αoperation␈α
is
␈↓ ↓H␈↓(␈↓¬LSH␈↓ <n> <d>).

␈↓ ↓H␈↓        Boolean␈α∞operations␈α∞are␈α∞particularly␈α∞useful␈α∞when␈α∞you␈α∞have␈α∞a␈α∞problem␈α∞involving␈α∞data␈α
that
␈↓ ↓H␈↓can␈α∞easily␈α∞be␈α
represented␈α∞by␈α∞bit␈α∞strings␈α
or␈α∞vectors.␈α∞ Using␈α∞the␈α
Boolean␈α∞operations␈α∞is␈α∞very␈α
much
␈↓ ↓H␈↓more␈α⊂efficient␈α⊃than␈α⊂representing␈α⊃the␈α⊂same␈α⊂data␈α⊃as␈α⊂lists␈α⊃of␈α⊂␈↓¬0␈↓s␈α⊂and␈α⊃␈↓¬1␈↓s,␈α⊂both␈α⊃in␈α⊂terms␈α⊃of␈α⊂space
␈↓ ↓H␈↓required␈α⊂and␈α⊂in␈α⊂terms␈α⊂of␈α∂computation␈α⊂time.␈α⊂ It␈α⊂does␈α⊂not␈α∂necessarily␈α⊂make␈α⊂the␈α⊂problem␈α⊂or␈α∂the
␈↓ ↓H␈↓programs␈α
easier␈α
to␈αunderstand,␈α
however.␈α
  We␈α
will␈αsee␈α
an␈α
example␈α
of␈αa␈α
problem␈α
solved␈αusing␈α
both
␈↓ ↓H␈↓list and bit represtations in Chapter VII.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *23


␈↓ ↓H␈↓α␈↓ ε
Exercises

␈↓ ↓H␈↓        1. What boolean operation does ␈↓¬BOOLE ␈↓perform when <code>=␈↓¬11 ␈↓(decimal)?

␈↓ ↓H␈↓        2. What <code> corresponds to the operation ␈↓¬x=y␈↓ ?



␈↓ ↓H␈↓11.  ␈↓αLambda expressions and functions with functions as arguments.␈↓


␈↓ ↓H␈↓        It␈αis␈αcommon␈αto␈α
use␈αphrases␈αlike␈α"the␈α
function␈α␈↓↓2x+y␈↓".␈α This␈αis␈α
not␈αa␈αprecise␈αnotation␈α
because
␈↓ ↓H␈↓we␈αcannot␈αsay␈α␈↓↓[2x+y][3, 4]␈↓␈αand␈αknow␈αwhether␈α
the␈αdesired␈αresult␈αis␈α2␈↓π*␈↓3+4␈αor␈α2␈↓π*␈↓4+3␈α
regarding␈αthe
␈↓ ↓H␈↓expression␈α⊃as␈α⊃a␈α⊃function␈α⊃of␈α⊃two␈α⊃variables.␈α⊃ Worse␈α⊃yet,␈α⊃we␈α⊃might␈α⊃have␈α⊃meant␈α∩a␈α⊃one-variable
␈↓ ↓H␈↓function of ␈↓↓x␈↓ wherein ␈↓↓y␈↓ is regarded as a parameter.

␈↓ ↓H␈↓        The␈αproblem␈αof␈αgiving␈αnames␈αto␈αfunctions␈αis␈αsolved␈αby␈αChurch's␈αλ-notation.␈α In␈αthe␈αabove
␈↓ ↓H␈↓example,␈αwe␈αwould␈αwrite␈α␈↓↓λx y: 2x+y␈↓␈αto␈αdenote␈αthe␈αfunction␈αof␈αtwo␈αvariables␈αwith␈αfirst␈αargument␈α␈↓↓x␈↓
␈↓ ↓H␈↓and␈α#second␈α"argument␈α#␈↓↓y␈↓␈α"whose␈α#value␈α#is␈α"given␈α#by␈α"the␈α#expression␈α#␈↓↓2x+y␈↓.␈α" Thus,
␈↓ ↓H␈↓␈↓↓[λx y: 2x+y][3, 4] = 10␈↓ and  ␈↓↓[λy x: 2x+y][3, 4]= 11.␈↓

␈↓ ↓H␈↓        Like␈α⊂variables␈α⊃of␈α⊂integration␈α⊂and␈α⊃the␈α⊂bound␈α⊂variables␈α⊃of␈α⊂quantifiers␈α⊂in␈α⊃logic,␈α⊂variables
␈↓ ↓H␈↓following␈α∪the␈α∪ λ ␈α∪are␈α∀bound␈α∪or␈α∪dummy␈α∪and␈α∪may␈α∀be␈α∪replaced␈α∪by␈α∪any␈α∪others␈α∀provided␈α∪the
␈↓ ↓H␈↓replacement␈α
is␈α
done␈α
consistently␈α
throughout␈α
the␈α
expression␈α
and␈α
does␈α
not␈α
make␈α
any␈αvariable␈α
bound
␈↓ ↓H␈↓by␈α
 λ ␈α
the␈α
same␈α
as␈α
a␈α
free␈α
variable␈α
in␈α
the␈α
expression.␈α
 Thus␈α
␈↓↓λx y: 2x+y␈↓␈α
represents␈α
the␈α
same␈α
function
␈↓ ↓H␈↓as␈α␈↓↓λy x: 2y+x␈↓␈αor␈α␈↓↓λu v: 2u+v␈↓␈α,␈αbut␈αin␈αthe␈αfunction␈αof␈αone␈αargument␈α␈↓↓λx: 2x+y␈↓,␈αwe␈αcannot␈αreplace␈αthe
␈↓ ↓H␈↓variable ␈↓↓x␈↓ by ␈↓↓y,␈↓ though we could replace it by ␈↓↓u.␈↓

␈↓ ↓H␈↓        λ-notation␈α∞plays␈α
two␈α∞important␈α
roles␈α∞in␈α
LISP.␈α∞ First,␈α
it␈α∞allows␈α
us␈α∞to␈α
rewrite␈α∞an␈α
expression
␈↓ ↓H␈↓containing␈αtwo␈αor␈αmore␈αoccurrences␈αof␈αthe␈αsame␈αsub-expression␈αin␈αsuch␈αa␈αway␈αthat␈αthe␈αexpression
␈↓ ↓H␈↓occurs␈α∪only␈α∩once.␈α∪Thus␈α∩␈↓↓(2x+1)␈↓∧4␈↓↓+3(2x+1)␈↓∧3␈↓␈α∪can␈α∩be␈α∪written␈α∩␈↓↓[λw: w␈↓∧4␈↓↓+3w␈↓∧3␈↓↓][2x+1]␈↓.␈α∪ This␈α∪can␈α∩save
␈↓ ↓H␈↓considerable␈αcomputation,␈α
and␈αcorresponds␈αto␈α
the␈αpractice␈αin␈α
sequential␈αprogramming␈αof␈α
assigning
␈↓ ↓H␈↓to␈αa␈α
variable␈αthe␈αvalue␈α
of␈αa␈αsub-expression␈α
that␈αoccurs␈αmore␈α
than␈αonce␈αin␈α
an␈αexpression␈αand␈α
then
␈↓ ↓H␈↓writing the expression in terms of the variable.  It is sometimes called λ-binding.

␈↓ ↓H␈↓        The␈α∂second␈α∂use␈α∂of␈α⊂λ-expressions␈α∂is␈α∂in␈α∂using␈α⊂functions␈α∂that␈α∂take␈α∂functions␈α⊂as␈α∂arguments.
␈↓ ↓H␈↓Suppose␈αwe␈αwant␈αto␈αform␈αa␈αnew␈αlist␈αfrom␈αan␈αold␈αone␈αby␈αapplying␈αa␈αfunction␈α␈↓↓f␈↓␈αto␈αeach␈αelement␈αof
␈↓ ↓H␈↓the list.  This can be done using the function ␈↓↓mapcar␈↓ defined by

␈↓ ↓H␈↓11.1) ␈↓ βG␈↓↓mapcar[f, u] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ f[␈↓αa|␈↓↓u] . mapcar[f, ␈↓αd|␈↓↓u]␈↓. 

␈↓ ↓H␈↓Such␈αa␈αfunction␈αis␈αcalled␈αa␈α␈↓↓functional␈↓␈αsince␈αone␈α(or␈αmore)␈αof␈αits␈αarguments␈αis␈αa␈αfunction.␈α ␈↓↓mapcar␈↓
␈↓ ↓H␈↓maps a function and a list into a list.  Some functionals map functions to functions.

␈↓ ↓H␈↓Suppose␈α⊃the␈α⊃operation␈α⊃we␈α⊃want␈α⊃to␈α⊃perform␈α⊃is␈α⊃squaring,␈α⊃and␈α⊃we␈α⊃want␈α⊃to␈α⊃apply␈α⊃it␈α⊃to␈α⊃the␈α⊃list
␈↓ ↓H␈↓␈↓¬(1 2 3 4 5 6 7)␈↓.  We have

␈↓ ↓H␈↓␈↓ β7␈↓↓mapcar[λx: x␈↓∧2␈↓↓, ␈↓¬(1 2 3 4 5 6 7)␈↓↓] = ␈↓¬(1 4 9 16 25 36 49)␈↓↓␈↓. 

␈↓ ↓H␈↓        [Some␈α∞implementations␈α∞of␈α∞LISP␈α∞allow␈α∞mapping␈α∞functions␈α∞to␈α∞take␈α∞an␈α∞arbitrary␈α∞number␈α∞of
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *24


␈↓ ↓H␈↓lists␈α
as␈α
arguments.␈α
 The␈α∞number␈α
of␈α
lists␈α
is␈α
the␈α∞number␈α
of␈α
arguments␈α
expected␈α
by␈α∞the␈α
functional
␈↓ ↓H␈↓argument␈αand␈αthe␈αmapping␈αterminates␈αwhen␈αthe␈αshortest␈αlist␈αis␈αexhausted.␈α Some␈αimplementations
␈↓ ↓H␈↓of LISP require the arguments in reverse order - functional argument second.]

␈↓ ↓H␈↓        A␈αmore␈αgenerally␈αuseful␈αoperation␈αthan␈α␈↓↓mapcar␈↓␈αis␈α␈↓↓maplist␈↓␈αin␈αwhich␈αthe␈αfunction␈αis␈αapplied
␈↓ ↓H␈↓to the successive sublists of the list rather than to the elements.  ␈↓↓maplist␈↓ is defined by

␈↓ ↓H␈↓11.2) ␈↓ βN␈↓↓maplist[f, u] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ f[u] . maplist[f, ␈↓αd|␈↓↓u]␈↓. 

␈↓ ↓H␈↓        As␈α⊃an␈α⊃application␈α⊂of␈α⊃␈↓↓maplist␈↓␈α⊃and␈α⊂functional␈α⊃arguments,␈α⊃we␈α⊂shall␈α⊃define␈α⊃a␈α⊃function␈α⊂for
␈↓ ↓H␈↓differentiating␈α_algebraic␈α_expressions␈α↔involving␈α_sums␈α_and␈α↔products.␈α_ The␈α_syntax␈α_for␈α↔such
␈↓ ↓H␈↓expressions␈α
was␈α
given␈α
in␈α
(9.2).␈α
 Recall,␈α
␈↓¬PLUS␈α
␈↓followed␈α
by␈α
a␈α
list␈α
of␈α
arguments␈α
denotes␈α
the␈α∞sum␈α
of
␈↓ ↓H␈↓these␈αarguments␈αand␈α
␈↓¬TIMES␈α␈↓followed␈αby␈α
a␈αlist␈αof␈αarguments␈α
denotes␈αtheir␈αproduct.␈α
 The␈αfunction
␈↓ ↓H␈↓␈↓↓diff[e, v]␈↓ gives the partial derivative of the expression ␈↓↓e␈↓ with respect to the variable ␈↓↓v.␈↓ We have


␈↓ ↓H␈↓␈↓ αx␈↓↓diff[e, v] ← ␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αif␈↓↓ ␈↓αat|␈↓↓e ␈↓αthen␈↓↓ [␈↓αif␈↓↓ e = v ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ 0]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬PLUS␈↓↓ ␈↓αthen␈↓↓ ␈↓¬PLUS␈↓↓ . mapcar[[λx: diff[x, v]], ␈↓αd|␈↓↓e]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬TIMES␈↓↓ ␈↓αthen␈↓↓ ␈↓
␈↓ ↓H␈↓11.3)␈↓ βX␈↓↓␈↓¬PLUS␈↓↓␈↓
␈↓ ↓H␈↓␈↓ βX␈↓↓. maplist[␈↓
␈↓ ↓H␈↓␈↓ βx␈↓↓[λx: ␈↓¬TIMES␈↓↓␈↓
␈↓ ↓H␈↓␈↓ ∧H␈↓↓. maplist[␈↓
␈↓ ↓H␈↓␈↓ ¬λ␈↓↓[λy: ␈↓αif␈↓↓ x = y ␈↓αthen␈↓↓ diff[␈↓αa|␈↓↓y, v] ␈↓αelse␈↓↓ ␈↓αa|␈↓↓y], ␈↓αd|␈↓↓e]], ␈↓
␈↓ ↓H␈↓␈↓ βx␈↓↓␈↓αd|␈↓↓e]␈↓


␈↓ ↓H␈↓The term that describes the rule for differentiating products corresponds to the rule

␈↓ ↓H␈↓␈↓ ∧&␈↓↓∂/∂v[␈↓πP␈↓↓␈↓βi␈↓↓ e␈↓βi␈↓↓] = ␈↓πS␈↓↓␈↓βi␈↓↓␈↓π P␈↓↓␈↓βj␈↓↓ [␈↓αif␈↓↓ i=j ␈↓αthen␈↓↓ ∂e␈↓βj␈↓↓/∂v ␈↓αelse␈↓↓ e␈↓βj␈↓↓] .␈↓ 

␈↓ ↓H␈↓and␈α∂␈↓↓maplist␈↓␈α⊂has␈α∂to␈α⊂be␈α∂used␈α⊂rather␈α∂than␈α⊂␈↓↓mapcar␈↓␈α∂since␈α⊂whether␈α∂to␈α⊂differentiate␈α∂in␈α⊂forming␈α∂the
␈↓ ↓H␈↓product is determined by equality of the indices ␈↓↓i␈↓ and ␈↓↓j␈↓ rather than equality of the terms ␈↓↓e␈↓βi␈↓ and ␈↓↓e␈↓βj␈↓.

␈↓ ↓H␈↓        The internal form for a λ-expression is

␈↓ ↓H␈↓␈↓ βO(␈↓¬LAMBDA ␈↓<list of variables> <expression to be evaluated>).

␈↓ ↓H␈↓Thus␈α
␈↓↓λx:␈α
diff[x,v]␈↓␈α
is␈α
written␈α
␈↓¬(LAMBDA␈α
(X)␈α
(DIFF␈α
X␈α
V))␈↓.␈α
 The␈α
internal␈α
form␈α
of␈α
of␈α
␈↓↓diff␈↓␈α
is␈α
given
␈↓ ↓H␈↓below.  Notice that the function arguments to ␈↓↓maplist␈↓ and ␈↓↓mapcar␈↓ have the form

␈↓ ↓H␈↓␈↓ ¬(␈↓¬FUNCTION ␈↓ <λ-expression>).

␈↓ ↓H␈↓This␈αis␈α
necessary␈αif␈α
the␈αdefinition␈α
is␈αto␈α
be␈αcompiled␈α
as␈αthe␈α
compiler␈αmust␈α
recognize␈αthe␈α
fact␈αthat
␈↓ ↓H␈↓the␈αfollowing␈α
code␈αmust␈α
be␈αcompiled␈αas␈α
a␈αfunction.␈α
 If␈αthe␈αdefinition␈α
is␈αonly␈α
to␈αbe␈αinterpreted␈α
then
␈↓ ↓H␈↓␈↓¬FUNCTION␈α␈↓␈αhas␈αthe␈αsame␈αeffect␈αas␈α␈↓¬QUOTE␈α␈↓and␈αin␈αfact␈αyou␈αmay␈αuse␈α␈↓¬QUOTE␈α␈↓␈αinstead␈αof␈α␈↓¬FUNCTION␈α␈↓in
␈↓ ↓H␈↓definitions that will only be interpreted by MACLISP.
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *25



␈↓ ↓H␈↓¬(DEFUN DIFF (E V)
␈↓ ↓H␈↓¬  (COND ((ATOM E) (COND ((EQ E V) 1) (T 0)))
␈↓ ↓H␈↓¬        ((EQ (CAR E) 'PLUS)
␈↓ ↓H␈↓¬         (CONS 'PLUS
␈↓ ↓H␈↓¬               (MAPCAR (FUNCTION (LAMBDA (X) (DIFF X V))) (CDR E))))
␈↓ ↓H␈↓¬        ((EQ (CAR E) 'TIMES)
␈↓ ↓H␈↓¬         (CONS 'PLUS
␈↓ ↓H␈↓¬               (MAPLIST (FUNCTION
␈↓ ↓H␈↓¬                          (LAMBDA (X)
␈↓ ↓H␈↓¬                            (CONS 'TIMES
␈↓ ↓H␈↓¬                                  (MAPLIST (FUNCTION
␈↓ ↓H␈↓¬                                            (LAMBDA (Y)
␈↓ ↓H␈↓¬                                              (COND ((EQ X Y) (DIFF (CAR Y) V))
␈↓ ↓H␈↓¬                                                    (T (CAR Y)))))
␈↓ ↓H␈↓¬                                           (CDR E)))))
␈↓ ↓H␈↓¬                        (CDR E))))))


␈↓ ↓H␈↓        The␈α
above␈α
paragraphing␈α
(known␈α
as␈α"pretty␈α
printing")␈α
makes␈α
function␈α
definitions␈α
easier␈αto
␈↓ ↓H␈↓read because items beginning in the same column are at the same parenthetical level.

␈↓ ↓H␈↓        Two␈α∩additional␈α⊃useful␈α∩functions␈α⊃with␈α∩functions␈α⊃as␈α∩arguments␈α⊃are␈α∩the␈α⊃predicates  ␈↓↓andlis␈↓
␈↓ ↓H␈↓ and  ␈↓↓orlis␈↓  defined by the equations


␈↓ ↓H␈↓11.4) ␈↓ ∧∞␈↓↓andlis[p, u] ← ␈↓αn|␈↓↓u ␈↓αor␈↓↓ [p[␈↓αa|␈↓↓u] ␈↓αand␈↓↓ andlis[p, ␈↓αd|␈↓↓u]]␈↓

␈↓ ↓H␈↓11.5) ␈↓ ∧β␈↓↓ orlis[p, u] ← ␈↓αnot␈↓↓ ␈↓αn|␈↓↓u ␈↓αand␈↓↓ [p[␈↓αa|␈↓↓u] ␈↓αor␈↓↓ orlis[p, ␈↓αd|␈↓↓u]]␈↓.


␈↓ ↓H␈↓        Another␈α∂way␈α∂of␈α∂writing␈α∂function␈α∂definitions␈α∞in␈α∂internal␈α∂notation␈α∂uses␈α∂␈↓¬LAMBDA␈α∂␈↓to␈α∂make␈α∞a
␈↓ ↓H␈↓function of the right side of a definition.  It is like writing ␈↓↓subst␈↓ and ␈↓↓alt␈↓ as


␈↓ ↓H␈↓␈↓ α∪␈↓↓subst ← λx y z:[␈↓αif␈↓↓ ␈↓αat|␈↓↓z ␈↓αthen␈↓↓ [␈↓αif␈↓↓ z ␈↓αeq␈↓↓ y ␈↓αthen␈↓↓ x ␈↓αelse␈↓↓ z]  ␈↓αelse␈↓↓ subst[x,y,␈↓αa|␈↓↓z] . subst[x,y,␈↓αd|␈↓↓z]]␈↓

␈↓ ↓H␈↓␈↓ ∧α␈↓↓alt ← λu.[␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓u ␈↓αthen␈↓↓ u ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u . alt ␈↓αdd|␈↓↓u]␈↓.


␈↓ ↓H␈↓Internally these definitions of ␈↓↓subst␈↓ and ␈↓↓alt␈↓ take the forms

␈↓ ↓H␈↓¬␈↓ α((DEFPROP SUBST
␈↓ ↓H␈↓¬␈↓ α(  (LAMBDA (X Y Z)
␈↓ ↓H␈↓¬␈↓ α(    (COND ((ATOM Z) (COND ((EQ Z X) Y) (T Z)))
␈↓ ↓H␈↓¬␈↓ α(          (T (CONS (SUBST X Y (CAR Z)) (SUBST X Y (CDR Z))))))
␈↓ ↓H␈↓¬␈↓ α( EXPR)


␈↓ ↓H␈↓¬␈↓ α((DEFPROP ALT
␈↓ ↓H␈↓¬␈↓ α(  (LAMBDA (U) (COND ((OR (NULL U) (NULL (CDR U))) U)
␈↓ ↓H␈↓¬␈↓ α(                    (T (CONS (CAR U) (ALT (CDDR U))))))
␈↓ ↓H␈↓¬␈↓ α( EXPR).
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *26


␈↓ ↓H␈↓        The general form for this manner of writing functon definitions is

␈↓ ↓H␈↓␈↓ β?(␈↓¬DEFPROP ␈↓<function name> <defining λ-expression> ␈↓¬EXPR) ␈↓

␈↓ ↓H␈↓and␈α⊂it␈α⊃is␈α⊂often␈α⊃used␈α⊂by␈α⊃programs␈α⊂that␈α⊃output␈α⊂LISP.␈α⊂ It␈α⊃is␈α⊂a␈α⊃special␈α⊂case␈α⊃of␈α⊂an␈α⊃operation␈α⊂on
␈↓ ↓H␈↓property␈α
lists.␈α It␈α
puts␈α
the␈αλ-expression␈α
on␈α
the␈α␈↓¬EXPR␈α
␈↓property␈αof␈α
the␈α
function␈αname␈α
(which␈α
is␈αan
␈↓ ↓H␈↓atom).␈α
 ␈↓¬EXPR␈α␈↓says␈α
that␈α
the␈αitem␈α
is␈α
a␈αLISP␈α
function␈α
defined␈αby␈α
an␈α
S-expression.␈α (Rather␈α
than␈αby␈α
a
␈↓ ↓H␈↓machine␈αlanguage␈αsubroutine,␈αfor␈αinstance).␈α The␈α␈↓¬DEFUN␈α␈↓form␈αof␈αfunction␈αdefinition␈αhas␈αthe␈αsame
␈↓ ↓H␈↓effect␈αin␈αthat␈α
it␈αforms␈αa␈αλ-expression␈α
out␈αof␈αthe␈αlist␈α
of␈αvariables␈αand␈αthe␈α
right␈αhand␈αside␈αand␈α
puts
␈↓ ↓H␈↓it on the ␈↓¬EXPR ␈↓property of the function name.


␈↓ ↓H␈↓α␈↓ ε
Exercises

␈↓ ↓H␈↓        1.␈α∂Compute␈α∞␈↓↓diff[␈↓¬(TIMES␈α∂X␈α∂(PLUS␈α∞Y␈α∂1)␈α∞3),␈α∂X␈↓↓]␈↓␈α∂using␈α∞the␈α∂above␈α∞definition␈α∂of␈α∂␈↓↓diff.␈↓␈α∞ Now
␈↓ ↓H␈↓do you see why algebraic simplification is important?

␈↓ ↓H␈↓        2. Compute ␈↓↓orlis[␈↓αat␈↓↓, ␈↓¬((A B) (C D) E)␈↓↓]␈↓.

␈↓ ↓H␈↓        3. Evaluate the S-expression

␈↓ ↓H␈↓␈↓¬((LAMBDA␈α∩(X)␈α∪(LIST␈α∩X␈α∪(LIST␈α∩(QUOTE␈α∪QUOTE)␈α∩X)))␈α∪(QUOTE␈α∩(LAMBDA␈α∪(X)␈α∩(LIST␈α∪X␈α∩(LIST
␈↓ ↓H␈↓¬(QUOTE QUOTE) X)))))␈↓

␈↓ ↓H␈↓and␈α∞say␈α
what␈α∞its␈α
interesting␈α∞property␈α
is.␈α∞ Variants␈α
of␈α∞this␈α
expression␈α∞have␈α∞important␈α
theoretical
␈↓ ↓H␈↓properties.



␈↓ ↓H␈↓12.  ␈↓αLabel.␈↓


␈↓ ↓H␈↓        The␈αλ␈α
mechanism␈αis␈α
not␈αadequate␈α
for␈αproviding␈α
names␈αfor␈α
recursive␈αfunctions,␈α
because␈αin
␈↓ ↓H␈↓this␈αcase␈αthere␈αhas␈αto␈αbe␈αa␈αway␈αof␈αreferring␈αto␈αthe␈αfunction␈αname␈αwithin␈αthe␈αfunction.␈α Therefore,
␈↓ ↓H␈↓we␈α∞use␈α∞the␈α∞notation  ␈↓↓label[f, e]␈↓  to␈α∞denote␈α∞the␈α∞expression␈α∞␈↓↓e␈↓␈α∞but␈α∞where␈α∞occurrences␈α∞of␈α∞␈↓↓f␈↓␈α∂within␈α∞␈↓↓e␈↓
␈↓ ↓H␈↓refer␈α∞to␈α∞the␈α
whole␈α∞expression.␈α∞ For␈α∞example,␈α
suppose␈α∞we␈α∞wished␈α∞to␈α
define␈α∞a␈α∞function␈α∞that␈α
takes
␈↓ ↓H␈↓alternate elements of each element of a list and makes a list of these.  Thus, we want

␈↓ ↓H␈↓␈↓ β→␈↓↓altlis[␈↓¬((A B C) (A B C D) (X Y Z))␈↓↓] = ␈↓¬((A C) (A C) (X Z))␈↓↓␈↓. 

␈↓ ↓H␈↓We can make the definition

␈↓ ↓H␈↓12.1) ␈↓ αP␈↓↓altlis[u] ← mapcar[label[alt, λu: ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αor␈↓↓ ␈↓αn|␈↓↓␈↓αd|␈↓↓u ␈↓αthen␈↓↓ u ␈↓αelse␈↓↓ ␈↓αa|␈↓↓u . alt[␈↓αdd|␈↓↓u]], u]␈↓. 

␈↓ ↓H␈↓in internal form this would be written
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *27



␈↓ ↓H␈↓¬␈↓ α((DEFUN ALTLIS (X)
␈↓ ↓H␈↓¬␈↓ α(  (MAPCAR (QUOTE (LABEL ALT
␈↓ ↓H␈↓¬␈↓ α(                   (LAMBDA (X)
␈↓ ↓H␈↓¬␈↓ α(                     (COND (OR (NULL X) (NULL (CDR X))) X)
␈↓ ↓H␈↓¬␈↓ α(                           (T (CONS (CAR X) (ALT (CDDR X)))))))
␈↓ ↓H␈↓¬␈↓ α(           X)).

␈↓ ↓H␈↓        The general internal form of the label construct is

␈↓ ↓H␈↓␈↓ ∧F(␈↓¬LABEL ␈↓<name> <function expression>),

␈↓ ↓H␈↓        The␈α
identifier␈α
␈↓↓alt␈↓␈α
in␈α
the␈α
above␈α
example␈α
is␈α
bound␈α
by␈α
␈↓↓label␈↓␈α
and␈α
is␈α
local␈α
to␈α∞that␈α
expression,
␈↓ ↓H␈↓and␈α
this␈α
is␈α
the␈α
general␈α
rule.␈α
 The␈α
label␈α
construct␈αis␈α
not␈α
often␈α
used␈α
in␈α
LISP␈α
since␈α
it␈α
is␈α
more␈αusual␈α
to
␈↓ ↓H␈↓give functions global definitions.



␈↓ ↓H␈↓13.  ␈↓αThe function ␈↓↓eval.␈↓α ␈↓


␈↓ ↓H␈↓        ␈↓↓eval␈↓␈αplays␈αboth␈αa␈αtheoretical␈αand␈αa␈αpractical␈αrole␈αin␈αLISP.␈α Historically,␈αthe␈αlist␈αnotation␈αfor
␈↓ ↓H␈↓LISP␈αfunctions␈αand␈α␈↓↓eval␈↓␈α
were␈αfirst␈αdevised␈αin␈α
order␈αto␈αshow␈αhow␈αeasy␈α
it␈αis␈αto␈αdefine␈α
a␈αuniversal
␈↓ ↓H␈↓function␈α
in␈αLISP␈α
-␈αthe␈α
idea␈α
was␈αto␈α
advocate␈αLISP␈α
as␈α
an␈αalternative␈α
to␈αTuring␈α
machines␈αfor␈α
doing
␈↓ ↓H␈↓the␈α∂elementary␈α⊂theory␈α∂of␈α∂computability.␈α⊂ This␈α∂role␈α∂will␈α⊂be␈α∂discussed␈α∂in␈α⊂a␈α∂later␈α∂chapter.␈α⊂  S.␈α∂R.
␈↓ ↓H␈↓Russell␈α∞noted␈α∞that␈α∞␈↓↓eval␈↓␈α∞could␈α∞serve␈α∞as␈α∞an␈α∞interpreter␈α∞for␈α∞LISP␈α∞and␈α∞promptly␈α∞programmed␈α∞it␈α∞in
␈↓ ↓H␈↓machine␈α
language␈α
with␈α
minor␈α
modifications␈α
to␈α
make␈α
it␈α
more␈α
practical.␈α
 An␈α
interpreter␈α
based␈α
on
␈↓ ↓H␈↓␈↓↓eval␈↓␈αhas␈αremained␈αa␈αfeature␈αof␈αmost␈αLISP␈αsystems.␈α Thus␈αwhen␈αyou␈αtalking␈αto␈αLISP␈αthe␈αsystem␈αis
␈↓ ↓H␈↓in␈αa␈αloop␈αthat␈α␈↓↓read␈↓s␈αwhat␈αyou␈αtype,␈α␈↓↓eval␈↓s␈αit␈αand␈α␈↓↓print␈↓s␈αthe␈αresult.␈α  [Of␈αcourse␈αa␈αreal␈αLISP␈αsystem
␈↓ ↓H␈↓does many other things too, such a storage management, error handling, etc.]

␈↓ ↓H␈↓        ␈↓↓eval␈↓␈αfor␈αLISP␈αexpressions␈αis␈αanalogous␈αto␈αthe␈αinterpreter␈α␈↓↓numval␈↓␈αfor␈αarithmetic␈αexpressions
␈↓ ↓H␈↓given␈αin␈α(9.4).␈α The␈αfirst␈αargument␈αto␈α␈↓↓eval␈↓␈αis␈αa␈αLISP␈αexpression␈αin␈αinternal␈αnotation.␈α The␈αsecond
␈↓ ↓H␈↓argument␈α∞is␈α∂an␈α∞association␈α∞list␈α∂that␈α∞tells␈α∞␈↓↓eval␈↓␈α∂what␈α∞value␈α∞each␈α∂variable␈α∞has,␈α∞and␈α∂what␈α∞function
␈↓ ↓H␈↓definition␈αis␈αto␈αbe␈αassociated␈αwith␈αeach␈αfunction␈αname.␈α Thus␈αthe␈αassociation␈αlist␈αis␈αa␈αlist␈αof␈αpairs
␈↓ ↓H␈↓where␈αeach␈α
pair␈αconsists␈α
either␈αof␈α
a␈αvariable␈α
and␈αthe␈α
S-expression␈αcorresponding␈α
to␈αits␈α
value,␈αor␈α
a
␈↓ ↓H␈↓function␈α
name␈α∞and␈α
the␈α∞S-expression␈α
representing␈α∞the␈α
function␈α∞expression␈α
defining␈α∞the␈α
function.
␈↓ ↓H␈↓(Here␈α∂a␈α∂function␈α∂expression␈α∂is␈α∞either␈α∂a␈α∂function␈α∂name,␈α∂or␈α∞a␈α∂lambda␈α∂expression.)␈α∂The␈α∂result␈α∞of
␈↓ ↓H␈↓applying␈α␈↓↓eval␈↓␈αis␈αthe␈αvalue␈αof␈αthe␈α
term␈αrepresented␈αby␈αthe␈αS-expression␈αin␈αan␈α
environment␈αwhere
␈↓ ↓H␈↓the␈α∞free␈α∂variables␈α∞are␈α∞assigned␈α∂the␈α∞values␈α∞given␈α∂by␈α∞the␈α∞association␈α∂list␈α∞and␈α∞where␈α∂the␈α∞function
␈↓ ↓H␈↓names␈α∪occuring␈α∩free␈α∪(i.e.␈α∩not␈α∪bound␈α∩in␈α∪a␈α∩label␈α∪expression)␈α∩denote␈α∪functions␈α∩defined␈α∪by␈α∩the
␈↓ ↓H␈↓associated expressions in the association list.

␈↓ ↓H␈↓        Since␈αany␈αcomputation␈αcan␈αbe␈αdescribed␈αas␈αevaluating␈αan␈αexpression␈αwithout␈αfree␈αvariables
␈↓ ↓H␈↓or␈α∀function␈α∀names,␈α∀the␈α∀second␈α∀argument␈α∀theoretically␈α∀plays␈α∀a␈α∀role␈α∀mainly␈α∀in␈α∃the␈α∀recursive
␈↓ ↓H␈↓definition of ␈↓↓eval.␈↓  Thus we usually start our computations with the second argument ␈↓¬NIL␈↓.

␈↓ ↓H␈↓        To␈αillustrate␈αthis,␈αsuppose␈αwe␈αwant␈αto␈αapply␈αthe␈αfunction␈α␈↓↓alt␈↓␈αto␈αthe␈αlist␈α␈↓¬(A␈αB␈αC␈αD␈αE)␈↓,␈αi.e.␈αwe
␈↓ ↓H␈↓wish to evaluate ␈↓↓alt[␈↓¬(A B C D E)␈↓↓]␈↓.  This can be obtained by computing

␈↓ ↓H␈↓                      ␈↓↓eval[␈↓␈↓¬((LABEL ALT␈↓
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *28


␈↓ ↓H␈↓                                  ␈↓¬(LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X)␈↓
␈↓ ↓H␈↓                                                           ␈↓¬(T (CONS (CAR X) (ALT (CDDR X)))))))␈↓
␈↓ ↓H␈↓                                 ␈↓¬(QUOTE (A B C D E)))␈↓,
␈↓ ↓H␈↓                              ␈↓↓␈↓¬NIL␈↓↓]␈↓,

␈↓ ↓H␈↓which gives the expected result ␈↓¬(A C E)␈↓.

␈↓ ↓H␈↓        This␈α∂manner␈α∞of␈α∂evaluating␈α∞requires␈α∂that␈α∞auxiliary␈α∂functions␈α∞must␈α∂be␈α∞defined␈α∂within␈α∞any
␈↓ ↓H␈↓expression␈αwhere␈αthey␈αare␈αused␈α(by␈αusing␈αthe␈αlabel␈αconstruct)␈αand␈αworse␈αyet,␈αthey␈αmust␈αbe␈αdefined
␈↓ ↓H␈↓separately␈α↔for␈α⊗separate␈α↔occurrences.␈α⊗  This␈α↔can␈α⊗become␈α↔very␈α⊗cumbersome␈α↔and␈α↔also␈α⊗makes
␈↓ ↓H␈↓expressions␈α∞fairly␈α∞difficult␈α
to␈α∞understand.␈α∞ Another␈α
approach␈α∞is␈α∞to␈α
use␈α∞an␈α∞association␈α∞list␈α
which
␈↓ ↓H␈↓associates␈α⊗each␈α∃function␈α⊗name␈α⊗appearing␈α∃in␈α⊗the␈α⊗expression␈α∃with␈α⊗the␈α⊗appropriate␈α∃defining
␈↓ ↓H␈↓expression.   Thus we could evaluate ␈↓↓alt[␈↓¬(A B C D E)␈↓↓]␈↓ by computing

␈↓ ↓H␈↓↓                        eval[␈↓¬(ALT (QUOTE (A B C D E)))␈↓↓,
␈↓ ↓H␈↓↓                              ␈↓¬((ALT LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X)␈↓↓
␈↓ ↓H␈↓↓                                                           ␈↓¬(T (CONS (CAR X) (ALT (CDDR X)))))))␈↓↓].

␈↓ ↓H␈↓        A simplified version of the usual LISP ␈↓↓eval␈↓ is the following:

␈↓ ↓H␈↓␈↓ α8␈↓↓eval[e, a] ←␈↓
␈↓ ↓H␈↓␈↓ αx␈↓↓␈↓αif␈↓↓ ␈↓αat|␈↓↓e ␈↓αthen␈↓↓ [␈↓αif␈↓↓ numberp e ␈↓αor␈↓↓ e  = ␈↓¬NIL␈↓↓ ␈↓αor␈↓↓ e = ␈↓¬T␈↓↓ ␈↓αthen␈↓↓ e  ␈↓αelse␈↓↓ ␈↓αd|␈↓↓assoc[e, a]]␈↓
␈↓ ↓H␈↓␈↓ αx␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αat|␈↓↓␈↓αa|␈↓↓e ␈↓αthen␈↓↓␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓[␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬QUOTE ␈↓↓␈↓αthen␈↓↓ ␈↓αad|␈↓↓e␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬COND ␈↓↓␈↓αthen␈↓↓ evcond[␈↓αd|␈↓↓e, a]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬LIST ␈↓↓␈↓αthen␈↓↓ evlist[␈↓αd|␈↓↓e,a]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬CAR ␈↓↓␈↓αthen␈↓↓ ␈↓αa|␈↓↓eval[␈↓αad|␈↓↓e, a]␈↓
␈↓ ↓H␈↓13.1)␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬CDR ␈↓↓␈↓αthen␈↓↓ ␈↓αd|␈↓↓eval[␈↓αad|␈↓↓e, a]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬CONS ␈↓↓␈↓αthen␈↓↓ eval[␈↓αad|␈↓↓e, a] . eval[␈↓αadd|␈↓↓e, a]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬ATOM ␈↓↓␈↓αthen␈↓↓ ␈↓αat|␈↓↓eval[␈↓αad|␈↓↓e, a]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αa|␈↓↓e = ␈↓¬EQ ␈↓↓␈↓αthen␈↓↓  eval[␈↓αad|␈↓↓e, a] ␈↓αeq␈↓↓ eval[␈↓αadd|␈↓↓e, a]␈↓
␈↓ ↓H␈↓␈↓ β8␈↓↓␈↓αelse␈↓↓ eval[␈↓αd|␈↓↓assoc[␈↓αa|␈↓↓e, a] . ␈↓αd|␈↓↓e, a]]␈↓
␈↓ ↓H␈↓␈↓ αx␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αaa|␈↓↓e = ␈↓¬LAMBDA ␈↓↓␈↓αthen␈↓↓ eval[␈↓αadda|␈↓↓e, prup[␈↓αada|␈↓↓e, evlist[␈↓αd|␈↓↓e,a]] * a]␈↓
␈↓ ↓H␈↓␈↓ αx␈↓↓␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αaa|␈↓↓e = ␈↓¬LABEL ␈↓↓␈↓αthen␈↓↓ eval[␈↓αadda|␈↓↓e . ␈↓αd|␈↓↓e, [␈↓αada|␈↓↓e . ␈↓αadda|␈↓↓e] . a]␈↓,


␈↓ ↓H␈↓where the auxiliary functions ␈↓↓evcond␈↓ and ␈↓↓evlist␈↓ are defined by

␈↓ ↓H␈↓13.2) ␈↓ α⎇␈↓↓evcond[u, a] ← ␈↓αif␈↓↓ eval[␈↓αaa|␈↓↓u, a] ␈↓αthen␈↓↓ eval[␈↓αada|␈↓↓u, a]  ␈↓αelse␈↓↓ evcond[␈↓αd|␈↓↓u, a]␈↓, 

␈↓ ↓H␈↓13.3) ␈↓ β<␈↓↓evlist[u, a] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ eval[␈↓αa|␈↓↓u,a] . evlist[␈↓αd|␈↓↓u, a]␈↓, 

␈↓ ↓H␈↓and␈αthe␈αauxiliary␈αfunction␈α␈↓↓prup,␈↓␈αused␈αfor␈αpairing␈αup␈αthe␈αelements␈αof␈αtwo␈αlists␈αof␈αequal␈αlength,␈αis
␈↓ ↓H␈↓defined by

␈↓ ↓H␈↓13.4) ␈↓ βA␈↓↓prup[u, v] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓u ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ [␈↓αa|␈↓↓u . ␈↓αa|␈↓↓v] . prup[␈↓αd|␈↓↓u,␈↓αd|␈↓↓v]␈↓. 

␈↓ ↓H␈↓Recall that ␈↓↓assoc␈↓ is defined by

␈↓ ↓H␈↓13.5) ␈↓ α{␈↓↓assoc[x,a] ← ␈↓αif␈↓↓ ␈↓αn|␈↓↓a ␈↓αthen␈↓↓ ␈↓¬NIL␈↓↓ ␈↓αelse␈↓↓ ␈↓αif␈↓↓ ␈↓αaa|␈↓↓a ␈↓αeq␈↓↓ x ␈↓αthen␈↓↓ ␈↓αa|␈↓↓a ␈↓αelse␈↓↓ assoc[x,␈↓αd|␈↓↓a].␈↓ 
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *29


␈↓ ↓H␈↓        This␈α⊂simple␈α⊃␈↓↓eval␈↓␈α⊂expects␈α⊃that␈α⊂an␈α⊃expression␈α⊂is␈α⊃either␈α⊂a␈α⊃constant␈α⊂(␈↓↓number,␈↓␈α⊃␈↓¬T␈↓,␈α⊂␈↓¬NIL␈↓,␈α⊃or␈α⊂a
␈↓ ↓H␈↓␈↓¬QUOTE␈↓d␈αS-expression),␈αa␈αvariable␈α
whose␈αvalue␈αcan␈αbe␈αfound␈α
on␈αthe␈αassociation␈αlist,␈α
a␈αconditional
␈↓ ↓H␈↓expression,␈α
a␈αlist␈α
making␈αexpression,␈α
or␈αan␈α
application␈αof␈α
a␈αfunction,␈α
lambda␈αexpression␈α
or␈αlabel
␈↓ ↓H␈↓expression␈α∩to␈α∩a␈α∩list␈α∩of␈α∩arguments.␈α∩ Thus␈α∪␈↓↓eval␈↓␈α∩checks␈α∩to␈α∩see␈α∩which␈α∩of␈α∩the␈α∩above␈α∪classes␈α∩the
␈↓ ↓H␈↓expression␈α
to␈α
be␈α
evaluated␈α
falls␈α
into␈α
and␈α
proceeds␈α
accordingly.␈α
 If␈α
the␈α
expression,␈α
␈↓↓e,␈↓␈α
is␈α
atomic␈α
then
␈↓ ↓H␈↓it␈α∩is␈α∩either␈α∩a␈α∩non␈α⊃␈↓¬QUOTE␈↓d␈α∩constant␈α∩or␈α∩a␈α∩variable.␈α∩ If␈α⊃the␈α∩former␈α∩then␈α∩␈↓↓eval␈↓␈α∩just␈α∩returns␈α⊃the
␈↓ ↓H␈↓expression, if the latter it looks up the value on the association list, ␈↓↓a.␈↓

␈↓ ↓H␈↓        If␈α␈↓↓e␈↓␈αis␈αnon-atomic␈αbut␈α
␈↓αa|␈↓␈↓↓e␈↓␈αis␈αatomic␈αthen␈α␈↓↓e␈↓␈αis␈α
either␈αa␈α␈↓¬QUOTE␈↓d␈αconstant,␈αa␈αconditional,␈α
a␈αlist
␈↓ ↓H␈↓maker,␈αor␈αan␈αapplication␈αof␈αa␈αfunction␈αto␈αa␈αlist␈αof␈αarguments.␈α In␈αthe␈αconstant␈αcase␈αthe␈αexpression
␈↓ ↓H␈↓being␈α∂quoted␈α∞(␈↓αad|␈↓␈↓↓e)␈↓␈α∂is␈α∞returned.␈α∂ If␈α∞␈↓↓e␈↓␈α∂is␈α∂a␈α∞conditional␈α∂then␈α∞the␈α∂list␈α∞of␈α∂pairs␈α∞is␈α∂processed␈α∂by␈α∞the
␈↓ ↓H␈↓auxiliary␈α
evaluator␈α
␈↓↓evcond,␈↓␈α
which␈α
␈↓↓eval␈↓s␈α
the␈α
"if"␈α
parts␈α
(␈↓↓␈↓αaa|␈↓↓u␈↓)␈α
in␈α
order␈α
until␈α
a␈α
true␈α
one␈α
is␈α
found␈α
then
␈↓ ↓H␈↓returns␈α⊂the␈α∂result␈α⊂of␈α∂␈↓↓eval␈↓ing␈α⊂the␈α∂corresponding␈α⊂"then"␈α∂part␈α⊂(␈↓↓␈↓αada|␈↓↓u␈↓).␈α∂ In␈α⊂the␈α∂list␈α⊂case␈α∂the␈α⊂list␈α∂of
␈↓ ↓H␈↓expressions␈α
to␈α
be␈αevaluated␈α
is␈α
given␈αto␈α
␈↓↓evlist␈↓␈α
which␈α
returns␈αa␈α
list␈α
of␈αthe␈α
values.␈α
 In␈α
the␈αfunction
␈↓ ↓H␈↓application␈αcase␈αthere␈αare␈αtwo␈αpossibilities.␈α If␈αthe␈αfunction␈αto␈αbe␈αapplied␈αis␈αone␈αof␈αthe␈αelementary
␈↓ ↓H␈↓functions,␈α∀the␈α∀indicated␈α∀operation␈α∀is␈α∀performed␈α∀on␈α∀the␈α∀result␈α∀of␈α∀evaluating␈α∀the␈α∀arguments.
␈↓ ↓H␈↓Otherwise␈α
the␈α
function␈α
must␈α
be␈α
defined␈α
in␈α
␈↓↓a,␈↓␈α
so␈α
␈↓↓eval␈↓␈α
looks␈α
up␈α
the␈α
definition,␈α
replaces␈α
the␈α
function
␈↓ ↓H␈↓name by the function definition in the expression and restarts the evaluation.

␈↓ ↓H␈↓        If␈α
neither␈α␈↓↓e␈↓␈α
nor␈α␈↓αa|␈↓␈↓↓e␈↓␈α
are␈αatomic␈α
then␈αit␈α
must␈α
be␈αa␈α
lambda␈αor␈α
label␈αapplication.␈α
 In␈αthe␈α
lambda
␈↓ ↓H␈↓case␈αthe␈αargument␈α
list␈αis␈αgiven␈αto␈α
␈↓↓evlist␈↓␈αto␈αbe␈αevaluated,␈α
the␈αvalues␈αare␈αthen␈α
paired␈αwith␈αthe␈αlist␈α
of
␈↓ ↓H␈↓variables␈αto␈αbe␈αbound␈αby␈αthe␈αlambda␈α(␈↓αada|␈↓␈↓↓e)␈↓␈αusing␈α␈↓↓prup␈↓␈αand␈αput␈αon␈αthe␈αfront␈αof␈α␈↓↓a.␈↓␈αThe␈αbody␈αof
␈↓ ↓H␈↓the␈α∂lambda␈α∂(␈↓αadda|␈↓␈↓↓e)␈↓␈α∂is␈α∂then␈α⊂evaluated␈α∂using␈α∂this␈α∂new␈α∂association␈α⊂list.␈α∂ In␈α∂the␈α∂label␈α∂case␈α⊂a␈α∂new
␈↓ ↓H␈↓association␈α∩list␈α∩is␈α∩formed␈α∩by␈α∩pairing␈α⊃the␈α∩function␈α∩name␈α∩(␈↓αada|␈↓␈↓↓e)␈↓␈α∩with␈α∩the␈α∩defining␈α⊃expression
␈↓ ↓H␈↓(␈↓αadda|␈↓␈↓↓e)␈↓␈αand␈α
adding␈αthe␈α
result␈αto␈α
the␈αfront␈α
of␈α␈↓↓a.␈↓␈α
 Then␈αthe␈α
label␈αexpression␈α
is␈αreplaced␈α
in␈α␈↓↓e␈↓␈αby␈α
the
␈↓ ↓H␈↓defining expression and this is evaluated using the new association list.

␈↓ ↓H␈↓        If␈α∞␈↓↓e␈↓␈α
is␈α∞not␈α∞an␈α
expression␈α∞of␈α
the␈α∞sort␈α∞expected␈α
by␈α∞␈↓↓eval,␈↓␈α
then␈α∞the␈α∞result␈α
is␈α∞not␈α∞defined.␈α
  It
␈↓ ↓H␈↓would␈α
not␈α
be␈α
difficult␈α
to␈α
add␈α
additional␈α∞clauses␈α
to␈α
␈↓↓eval␈↓␈α
so␈α
that␈α
it␈α
would␈α
return␈α∞reasonable␈α
error
␈↓ ↓H␈↓messages␈αrather␈α
than␈αjust␈α
being␈αundefined␈α(or␈α
dying␈αin␈α
some␈αstrange␈αway␈α
as␈αwould␈α
be␈αlikely␈αin␈α
an
␈↓ ↓H␈↓actual␈α⊃computer).␈α⊃ It␈α⊃would␈α⊂be␈α⊃necessary␈α⊃to␈α⊃be␈α⊂make␈α⊃the␈α⊃error␈α⊃messages␈α⊃distinguishable␈α⊂from
␈↓ ↓H␈↓legitimate␈αvalues␈αof␈αthe␈αexpression␈αso␈αthat␈αerrors␈αat␈αinner␈αlevels␈αof␈αevaluation␈αcould␈αbe␈αpassed␈αup
␈↓ ↓H␈↓the␈αchain.␈α This␈αcould␈αbe␈αdone␈αby␈αreturning␈αlegitimate␈αvalues␈αas␈αpairs␈αwhose␈αfirst␈αelement␈αis␈αone
␈↓ ↓H␈↓atom␈α∂and␈α∂error␈α∂messages␈α⊂as␈α∂pairs␈α∂prefixed␈α∂by␈α∂another.␈α⊂ Terms␈α∂containing␈α∂␈↓↓eval␈↓␈α∂would␈α⊂have␈α∂to
␈↓ ↓H␈↓distinguish the cases.

␈↓ ↓H␈↓        Notice␈α⊗that␈α⊗␈↓¬COND␈α⊗␈↓and␈α⊗␈↓¬LIST␈α⊗␈↓considered␈α⊗as␈α⊗pseudo-functions␈α⊗behave␈α⊗differently␈α⊗than
␈↓ ↓H␈↓ordinary␈α⊃functions␈α⊃in␈α∩that␈α⊃both␈α⊃can␈α∩take␈α⊃an␈α⊃arbitrary␈α∩number␈α⊃of␈α⊃arguments␈α∩while␈α⊃functions
␈↓ ↓H␈↓defined␈α
by␈α
a␈α
lambda␈α
expression␈α
have␈α
a␈α
fixed␈α
number␈α
of␈α
arguments␈α
determined␈α
by␈α
the␈αvariable
␈↓ ↓H␈↓list␈αoccuring␈αin␈αthe␈αlambda␈αexpression.␈α Also,␈αthe␈αusual␈αmanner␈αof␈αevaluation␈αan␈αapplication␈αterm
␈↓ ↓H␈↓is␈αLISP␈αis␈αto␈αevaluate␈αall␈αof␈αthe␈αarguments␈αthen␈αapply␈αthe␈αfunction.␈α This␈αwill␈αnot␈αwork␈αfor␈α␈↓¬COND
␈↓ ↓H␈↓¬␈↓as␈αthe␈αmain␈αreason␈αfor␈αa␈αconditional␈αis␈αto␈αbe␈αable␈αto␈αselect␈αa␈αterm␈αto␈αevaluate␈αdepending␈αon␈αsome
␈↓ ↓H␈↓set of conditions and not to evaluate other terms under those conditions.

␈↓ ↓H␈↓        The␈α∞above␈α∞version␈α∞of␈α
␈↓↓eval␈↓␈α∞does␈α∞not␈α∞handle␈α∞the␈α
propositional␈α∞constructs␈α∞␈↓αand␈↓,␈α∞␈↓αor␈↓,␈α∞and␈α
␈↓αnot␈↓.
␈↓ ↓H␈↓The␈α
effect␈α∞of␈α
these␈α∞constructs␈α
can␈α
be␈α∞obtained␈α
by␈α∞appropriate␈α
use␈α
of␈α∞the␈α
condtional,␈α∞but␈α
simply
␈↓ ↓H␈↓defining␈α⊃functions␈α⊂for␈α⊃␈↓αand␈↓␈α⊂and␈α⊃␈↓αor␈↓␈α⊂will␈α⊃not␈α⊂work␈α⊃as␈α⊂the␈α⊃evaluation␈α⊂of␈α⊃a␈α⊃function␈α⊂application
␈↓ ↓H␈↓requires␈α
that␈α
all␈α
of␈α
the␈αarguments␈α
of␈α
of␈α
the␈α
function␈α
be␈αevaluated␈α
before␈α
it␈α
is␈α
applied␈α
while␈αthe
␈↓ ↓H␈↓specification␈α⊂of␈α⊂␈↓αand␈↓␈α⊂and␈α⊂␈↓αor␈↓␈α⊂require␈α⊂that␈α⊂only␈α⊂as␈α⊂many␈α⊂of␈α⊂the␈α⊂arguments␈α⊂be␈α⊂evaluated␈α⊃as␈α⊂are
␈↓ ↓H␈↓required␈α∂to␈α⊂determine␈α∂the␈α∂answer.␈α⊂ Another␈α∂problem␈α⊂is␈α∂that␈α∂in␈α⊂most␈α∂implementations␈α⊂they␈α∂are
␈↓ ↓H␈↓␈↓ εβChapter  I␈↓ *30


␈↓ ↓H␈↓allowed␈α∞to␈α
take␈α∞an␈α
arbitrary␈α∞number␈α
of␈α∞arguments.␈α∞  Thus␈α
we␈α∞need␈α
to␈α∞build␈α
them␈α∞into␈α∞␈↓↓eval␈↓␈α
for
␈↓ ↓H␈↓things␈α
to␈α
work␈α∞properly.␈α
 We␈α
will␈α
see␈α∞later␈α
that␈α
LISP␈α
systems␈α∞provide␈α
alternate␈α
solutions␈α∞to␈α
this
␈↓ ↓H␈↓problem␈α
by␈α
providing␈α
a␈α
variety␈α
of␈α
modes␈α
of␈α
functions␈α
application.␈α
 (These␈α
are␈α
known␈α∞as␈α
␈↓¬EXPR,
␈↓ ↓H␈↓¬␈↓␈↓¬FEXPR␈α⊃␈↓and␈α⊃␈↓¬LEXPR␈↓s.)␈α⊃   Arithmetic␈α∩is␈α⊃also␈α⊃missing␈α⊃from␈α∩our␈α⊃␈↓↓eval.␈↓␈α⊃ Adding␈α⊃these␈α∩constructs␈α⊃is
␈↓ ↓H␈↓essentially␈α∩like␈α⊃combining␈α∩␈↓↓eval␈↓␈α⊃with␈α∩the␈α∩earlier␈α⊃evaluator␈α∩␈↓↓numval␈↓␈α⊃and␈α∩adding␈α∩any␈α⊃additional
␈↓ ↓H␈↓primitive operations that are desired.

␈↓ ↓H␈↓        We␈α
note␈α∞that␈α
␈↓↓eval␈↓␈α
can␈α∞evaluate␈α
itself␈α∞if␈α
it␈α
is␈α∞given␈α
an␈α
association␈α∞list␈α
containing␈α∞the␈α
pairs
␈↓ ↓H␈↓␈↓¬(EVAL . λeval),␈α(␈↓␈↓¬(EVCOND . λevcond),␈α(␈↓␈↓¬(EVLIST . λevlist),␈α(␈↓␈α(␈↓¬(ASSOC . λassoc),
␈↓ ↓H␈↓¬␈↓␈↓¬(PRUP . λprup),␈α␈↓and␈α
␈↓¬(APPEND . λappend)␈α␈↓␈α
where␈α␈↓¬λ<function name>␈α
␈↓stands␈αfor␈α
the␈αinternal
␈↓ ↓H␈↓form of the expression defining the named function.  Thus

␈↓ ↓H␈↓␈↓ ∧'␈↓↓eval[␈↓¬(EVAL '(CAR '(A.B)) NIL)␈↓↓,alist] = ␈↓¬A␈↓↓␈↓ 

␈↓ ↓H␈↓where␈α
␈↓↓alist␈↓␈αis␈α
some␈αassociation␈α
list␈αcontaining␈α
the␈α
above␈αmentioned␈α
pairs␈α(and␈α
no␈αother␈α
definitions
␈↓ ↓H␈↓of those functions).

␈↓ ↓H␈↓        When␈αyou␈αtalk␈αto␈αLISP␈αyou␈αdo␈αnot␈αexplicitly␈αtell␈αthe␈αinterpreter␈αwhat␈αassociation␈αlist␈αto␈αuse
␈↓ ↓H␈↓generally.␈α
 This␈α
is␈αbecause␈α
the␈α
LISP␈α
associates␈αwith␈α
each␈α
atom␈α
a␈αlist␈α
of␈α
properties,␈α
 among␈αthese
␈↓ ↓H␈↓are␈α∂the␈α∂value,␈α∂and/or␈α∂the␈α∂function␈α∞definition␈α∂associated␈α∂with␈α∂that␈α∂atom.␈α∂ The␈α∂LISP␈α∞interpreter
␈↓ ↓H␈↓typically␈α∂looks␈α∂up␈α∂variable␈α∂values␈α∂and␈α∞function␈α∂definitions␈α∂on␈α∂the␈α∂corresponding␈α∂property␈α∞lists.
␈↓ ↓H␈↓Thus,␈α⊃instead␈α⊃of␈α⊃making␈α⊃up␈α⊃an␈α⊂association␈α⊃list␈α⊃with␈α⊃the␈α⊃appropriate␈α⊃variables␈α⊃and␈α⊂functions
␈↓ ↓H␈↓defined,␈αthe␈αproperty␈αlists␈αmust␈αfirst␈αbe␈αprimed␈αby␈αdoing␈α␈↓¬SETQ␈↓s␈αfor␈αgiving␈αvariables␈αinitial␈αvalues
␈↓ ↓H␈↓and␈α⊂␈↓¬DEFUN␈↓s␈α⊂(or␈α⊂␈↓¬DEFPROP␈↓s)␈α⊂for␈α∂any␈α⊂functions␈α⊂that␈α⊂need␈α⊂to␈α∂be␈α⊂defined.␈α⊂ These␈α⊂features␈α⊂will␈α∂be
␈↓ ↓H␈↓discussed in more detail in Chapter V.

␈↓ ↓H␈↓α␈↓ εεExercises.



␈↓ ↓H␈↓1. What is the value of

␈↓ ↓H␈↓    ␈↓↓eval[␈↓¬(LEFT (QUOTE (A . B)))␈↓↓,␈↓
␈↓ ↓H␈↓    ␈↓↓      ␈↓¬((LEFT LAMBDA (X) (COND ((ATOM X) X) (T (LEFT (CAR X))))))␈↓↓]␈↓?


␈↓ ↓H␈↓2. Translate the definition of ␈↓↓eval␈↓ given above into internal notation.

␈↓ ↓H␈↓3.␈αGo␈αto␈αyour␈αnearest␈αLISP␈αsystem,␈αtype␈αin␈αyour␈αanswer␈αto␈αthe␈αsecond␈αexercise␈αand␈αuse␈αit␈αto␈αcheck
␈↓ ↓H␈↓your answer to the first exercise.
␈↓ ↓H␈↓␈↓ εH␈↓ ?i


␈↓ ↓H␈↓α␈↓ ¬=FUNCTION INDEX

␈↓ ↓H␈↓alt   14
␈↓ ↓H␈↓altlis   26
␈↓ ↓H␈↓and   13
␈↓ ↓H␈↓andlis   25
␈↓ ↓H␈↓append   16
␈↓ ↓H␈↓assoc   21
␈↓ ↓H␈↓diff   24
␈↓ ↓H␈↓equal   16
␈↓ ↓H␈↓eval   28
␈↓ ↓H␈↓evcond   28
␈↓ ↓H␈↓evlist   28
␈↓ ↓H␈↓evplus   21
␈↓ ↓H␈↓evtimes   21
␈↓ ↓H␈↓fact   18
␈↓ ↓H␈↓flatten   17
␈↓ ↓H␈↓fringe   17
␈↓ ↓H␈↓gcd   18
␈↓ ↓H␈↓last   15
␈↓ ↓H␈↓length   20
␈↓ ↓H␈↓mapcar   23
␈↓ ↓H␈↓maplist   24
␈↓ ↓H␈↓member   16
␈↓ ↓H␈↓mod   18
␈↓ ↓H␈↓not   13
␈↓ ↓H␈↓numval   21
␈↓ ↓H␈↓or   13
␈↓ ↓H␈↓orlis   25
␈↓ ↓H␈↓prup   28
␈↓ ↓H␈↓reverse   17
␈↓ ↓H␈↓reversea   17
␈↓ ↓H␈↓subst   16
␈↓ ↓H␈↓␈↓ εH␈↓ 6ii


␈↓ ↓H␈↓α␈↓ ¬DDEFINED LABELS

␈↓ ↓H␈↓aa1   10                                  ␈↓ εh␈↓lists   1
␈↓ ↓H␈↓aa2   11                                  ␈↓ εh␈↓liststruc   3
␈↓ ↓H␈↓aa3   11                                  ␈↓ εh␈↓lsptrm   8
␈↓ ↓H␈↓aa4   12                                  ␈↓ εh␈↓mapcar    23
␈↓ ↓H␈↓aa5   12                                  ␈↓ εh␈↓maplist    24
␈↓ ↓H␈↓aa6   12                                  ␈↓ εh␈↓member    16
␈↓ ↓H␈↓ac4   13                                  ␈↓ εh␈↓mod d   18
␈↓ ↓H␈↓ac5   14                                  ␈↓ εh␈↓not t   13
␈↓ ↓H␈↓alpha   26                                ␈↓ εh␈↓numbers   19
␈↓ ↓H␈↓alt    14                                 ␈↓ εh␈↓numval    21
␈↓ ↓H␈↓altlis    26                              ␈↓ εh␈↓or r   13
␈↓ ↓H␈↓and d   13                                ␈↓ εh␈↓orlis    25
␈↓ ↓H␈↓andlis    25                              ␈↓ εh␈↓propop   13
␈↓ ↓H␈↓andor   13                                ␈↓ εh␈↓prup    28
␈↓ ↓H␈↓append    16                              ␈↓ εh␈↓recdefn   14
␈↓ ↓H␈↓assoc    21                               ␈↓ εh␈↓reverse    17
␈↓ ↓H␈↓assoc1   28                               ␈↓ εh␈↓reversea    17
␈↓ ↓H␈↓atoms   2                                 ␈↓ εh␈↓sexp   4
␈↓ ↓H␈↓basicfns   7                              ␈↓ εh␈↓subst    16
␈↓ ↓H␈↓bool   21
␈↓ ↓H␈↓boolcode   22
␈↓ ↓H␈↓cond   10
␈↓ ↓H␈↓diff    24
␈↓ ↓H␈↓equal    16
␈↓ ↓H␈↓eval l   28
␈↓ ↓H␈↓evaluator   27
␈↓ ↓H␈↓evcond    28
␈↓ ↓H␈↓evlist    28
␈↓ ↓H␈↓evplus    21
␈↓ ↓H␈↓evtimes    21
␈↓ ↓H␈↓expr   20
␈↓ ↓H␈↓f1   1
␈↓ ↓H␈↓f2   2
␈↓ ↓H␈↓f2a   3
␈↓ ↓H␈↓f3   3
␈↓ ↓H␈↓f4   4
␈↓ ↓H␈↓f5   5
␈↓ ↓H␈↓f5a   5
␈↓ ↓H␈↓f6   12
␈↓ ↓H␈↓fact    18
␈↓ ↓H␈↓flatten    17
␈↓ ↓H␈↓fringe    17
␈↓ ↓H␈↓gcd    18
␈↓ ↓H␈↓lambda   23
␈↓ ↓H␈↓last    15
␈↓ ↓H␈↓length h   20